Algorithm to determine coin combinations

I was recently faced with a prompt for a programming algorithm that I had no idea what to do for. I've never really written an algorithm before, so I'm kind of a newb at this.

The problem said to write a program to determine all of the possible coin combinations for a cashier to give back as change based on coin values and number of coins. For example, there could be a currency with 4 coins: a 2 cent, 6 cent, 10 cent and 15 cent coins. How many combinations of this that equal 50 cents are there?

The language I'm using is C++, although that doesn't really matter too much.

edit: This is a more specific programming question, but how would I analyze a string in C++ to get the coin values? They were given in a text document like

4 2 6 10 15 50 

(where the numbers in this case correspond to the开发者_开发百科 example I gave)

This problem is well known as coin change problem. Please check this and this for details. Also if you Google "coin change" or "dynamic programming coin change" then you will get many other useful resources.

Here's a recursive solution in Java:

// Usage: int[] denoms = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };       
// System.out.println(ways(denoms, denoms.length, 200));
public static int ways(int denoms[], int index, int capacity) {
    if (capacity == 0) return 1;
    if (capacity < 0 || index <= 0 ) return 0;
    int withoutItem = ways(denoms, index - 1, capacity); 
    int withItem = ways(denoms, index, capacity - denoms[index - 1]); 
    return withoutItem + withItem;
}

This seems somewhat like a Partition, except that you don't use all integers in 1:50. It also seems similar to bin packing problem with slight differences:

• Wikipedia: Partition (Number Theory)
• Wikipedia: Bin packing problem
• Wolfram Mathworld: Partiton

Actually, after thinking about it, it's an ILP, and thus NP-hard.

I'd suggest some dynamic programming appyroach. Basically, you'd define a value "remainder" and set it to whatever your goal was (say, 50). Then, at every step, you'd do the following:

1. Figure out what the largest coin that can fit within the remainder
2. Consider what would happen if you (A) included that coin or (B) did not include that coin.
3. For each scenario, recurse.

So if remainder was 50 and the largest coins were worth 25 and 10, you'd branch into two scenarios:

1. Remainder = 25, Coinset = 1x25
2. Remainder = 50, Coinset = 0x25

The next step (for each branch) might look like:

1-1. Remainder = 0,  Coinset = 2x25 <-- Note: Remainder=0 => Logged
1-2. Remainder = 25, Coinset = 1x25
2-1. Remainder = 40, Coinset = 0x25, 1x10
2-2. Remainder = 50, Coinset = 0x25, 0x10

Each branch would split into two branches unless:

• the remainder was 0 (in which case you would log it)
• the remainder was less than the smallest coin (in which case you would discard it)
• there were no more coins left (in which case you would discard it since remainder != 0)

If you have 15, 10, 6 and 2 cents coins and you need to find how many distinct ways are there to arrive to 50 you can

• count how many distinct ways you have to reach 50 using only 10, 6 and 2
• count how many distinct ways you have to reach 50-15 using only 10, 6 and 2
• count how many distinct ways you have to reach 50-15*2 using only 10, 6 and 2
• count how many distinct ways you have to reach 50-15*3 using only 10, 6 and 2
• Sum up all these results that are of course distinct (in the first I used no 15c coins, in the second I used one, in the third two and in the fourth three).

So you basically can split the problem in smaller problems (possibly smaller amount and fewer coins). When you have just one coin type the answer is of course trivial (either you cannot reach the prescribed amount exactly or you can in the only possible way).

Moreover you can also avoid repeating the same computation by using memoization, for example the number of ways of reach 20 using only [6, 2] doesn't depend if the already paid 30 have been reached using 15+15 or 10+10+10, so the result of the smaller problem (20, [6, 2]) can be stored and reused.

In Python the implementation of this idea is the following

cache = {}

def howmany(amount, coins):
    prob = tuple([amount] + coins) # Problem signature
    if prob in cache:
        return cache[prob] # We computed this before
    if amount == 0:
        return 1 # It's always possible to give an exact change of 0 cents
    if len(coins) == 1:
        if amount % coins[0] == 0:
            return 1 # We can match prescribed amount with this coin
        else:
            return 0 # It's impossible
    total = 0
    n = 0
    while n * coins[0] <= amount:
        total += howmany(amount - n * coins[0], coins[1:])
        n += 1
    cache[prob] = total # Store in cache to avoid repeating this computation
    return total

print howmany(50, [15, 10, 6, 2])

As for the second part of your question, suppose you have that string in the file coins.txt:

#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::ifstream coins_file("coins.txt");
    std::vector<int> coins;
    std::copy(std::istream_iterator<int>(coins_file),
              std::istream_iterator<int>(),
              std::back_inserter(coins));
}

Now the vector coins will contain the possible coin values.

For such a small number of coins you can write a simple brute force solution.

Something like this:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;

int solve(int total, int * coins, int lastI)
{
    if (total == 50) 
    {
        for (int i = 0; i < v.size(); i++)
        {
            cout << v.at(i) << ' ';
        }
        cout << "\n";
        return 1;
    }

    if (total > 50) return 0;

    int sum = 0;

    for (int i = lastI; i < 6; i++)
    {
        v.push_back(coins[i]);
        sum += solve(total + coins[i], coins, i); 
        v.pop_back();
    }

    return sum;
}


int main()
{
    int coins[6] = {2, 4, 6, 10, 15, 50};
    cout << solve(0, coins, 0) << endl;
}

A very dirty brute force solution that prints all possible combinations.

This is a very famous problem, so try reading about better solutions others have provided.

One rather dumb approach is the following. You build a mapping "coin with value X is used Y times" and then enumerate all possible combinations and only select those which total the desired sum. Obviously for each value X you have to check Y ranging from 0 up to the desired sum. This will be rather slow, but will solve your task.

It's very similar to the knapsack problem

You basically have to solve the following equation: 50 = a*4 + b*6 + c*10 + d*15, where the unknowns are a,b,c,d. You can compute for instance d = (50 - a*4 - b*6 - c*10)/15 and so on for each variable. Then, you start giving d all the possible values (you should start with the one that has the least possible values, here d): 0,1,2,3,4 and than start giving c all the possible values depending on the current value of d and so on.

Sort the List backwards: [15 10 6 4 2]

Now a solution for 50 ct can contain 15 ct or not. So the number of solutions is the number of solutions for 50 ct using [10 6 4 2] (no longer considering 15 ct coins) plus the number of solutions for 35 ct (=50ct - 15ct) using [15 10 6 4 2]. Repeat the process for both sub-problems.

An algorithm is a procedure for solving a problem, it doesn't have to be in any particular language.

First work out the inputs:

typedef int CoinValue;

set<CoinValue> coinTypes;
int value;

and the outputs:

set< map<CoinValue, int> > results;

Solve for the simplest case you can think of first:

coinTypes = { 1 }; // only one type of coin worth 1 cent
value = 51;

the result should be:

results = { [1 : 51] }; // only one solution, 51 - 1 cent coins

How would you solve the above?

How about this:

coinTypes = { 2 };
value = 51;

results = { }; // there is no solution

what about this?

coinTypes = { 1, 2 };
value = { 4 };

results = { [2: 2], [2: 1, 1: 2], [1: 4] }; // the order I put the solutions in is a hint to how to do the algorithm.

Recursive solution based on algorithmist.com resource in Scala:

def countChange(money: Int, coins: List[Int]): Int = {
    if (money < 0 || coins.isEmpty) 0
    else if (money == 0) 1
    else countChange(money, coins.tail) + countChange(money - coins.head, coins)
}

Another Python version:

def change(coins, money):
    return (
        change(coins[:-1], money) +
        change(coins, money - coins[-1])
        if money > 0 and coins
        else money == 0
    )