CS 3343, Making Change

CS3343/3341
Analysis of Algorithms

  Making Change
   with the
   Fewest Number of Coins

Making up Sums with "Coins": Suppose we have coins of various denominations, perhaps more than the standard 1, 5, 10, 25, and 50 that we commonly use, perhaps a strange set, such as 3, 7, 11, 15, 31, 47. We will use almost the same approach as with the Subset Sum problem. Here we may need more than one coin, so we will drop the condition that prevents repetitions. Since we don't want simple answers such as a sum of all pennies, we will add the condition that we want the fewest number of coins in our sums. For this we must not quit with the first sum we find.

In summary, make modifications to the old subset sum algorithm so that it will

allow repetitions,
try all sums, and
keep track of the number of "coins" (numbers) in a sum and reject all but the smallest number of coins that is produced.

For condition (1) above, leave off the second condition in the calcWork function. For condition (2) above, leave off the fourth condition in the calcWork function. To handle condition (3) above, introduce another "counting" array C parallel to the working array W. (Or separate fields in a class or struct.) The numbers in the C array let the algorithm keep track of the least number of coins produced at each stage. If a new number is less than the stored value, it replaces the table entry with the new one, and otherwise is sticks with the old table entry. (It might be convenient to set C[0] = 0, and all other C values equal to +infinity, or maybe just a big number, such as 10000.)

Here, along with each W (for "Work") entry, you are also to maintain a C (for "Count") entry. The C value gives the count of the smallest number of coins needed so far. In case a new count is equal or even greater than the old one, we leave both W and C alone for that index. In case the count of coins is less than the number stored in the C array, put the new (better) count into C, and the new value (last number added in) into the W array.

Let's work this all out for the previous example, with "coins" in an array A = {1,9,5,3,8}. If you do what was described above for this example, you get the following data. (The diagram shows at each stage, the W array with the C array below it in red. In the C array, 99 stands for +∞.)

Possible #s <------------- W Array Index ----- and ----- C Array Index -------------> in sum 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Initial: 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 {1}: W: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Count: C: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 {1,9}: W: 0 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 Count: C: 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 10 {1,9,5}: W: 0 1 1 1 1 5 5 5 5 9 9 9 9 9 5 5 5 5 9 9 9 9 9 5 5 5 5 Count: C: 0 1 2 3 4 1 2 3 4 1 2 3 4 5 2 3 4 5 2 3 4 5 6 3 4 5 6 {1,9,5,3}:W: 0 1 1 3 3 5 5 5 3 9 9 9 3 3 5 5 5 3 9 9 9 3 3 5 5 5 3 Count: C: 0 1 2 1 2 1 2 3 2 1 2 3 2 3 2 3 4 3 2 3 4 3 4 3 4 5 4 {1,9,5,3,8}W:0 1 1 3 3 5 5 5 8 9 9 8 3 8 5 5 8 8 9 9 8 3 8 5 8 8 8 Count: C: 0 1 2 1 2 1 2 3 1 1 2 2 2 2 2 3 2 2 2 3 3 3 3 3 3 3 3

Possible #s <------------- W Array Index ----- and ----- C Array Index -------------> in sum 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Initial: 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99
{1}: W: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Count: C: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
{1,9}: W: 0 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 Count: C: 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 10
{1,9,5}: W: 0 1 1 1 1 5 5 5 5 9 9 9 9 9 5 5 5 5 9 9 9 9 9 5 5 5 5 Count: C: 0 1 2 3 4 1 2 3 4 1 2 3 4 5 2 3 4 5 2 3 4 5 6 3 4 5 6
{1,9,5,3}:W: 0 1 1 3 3 5 5 5 3 9 9 9 3 3 5 5 5 3 9 9 9 3 3 5 5 5 3 Count: C: 0 1 2 1 2 1 2 3 2 1 2 3 2 3 2 3 4 3 2 3 4 3 4 3 4 5 4
{1,9,5,3,8}W:0 1 1 3 3 5 5 5 8 9 9 8 3 8 5 5 8 8 9 9 8 3 8 5 8 8 8 Count: C: 0 1 2 1 2 1 2 3 1 1 2 2 2 2 2 3 2 2 2 3 3 3 3 3 3 3 3

Let's look at a getting a total of 20, just as an example:

With just a single coin of value 1, we get a sum of 20 by taking 20 1-coins. We see that in the line labeled with "{1}:" and with the count of 20 below the entry of 1, under index 20.
The next line down adds a second coin with value 9. Here, under the index 20, we get 20 = 9+9+1+1, for a count of 4. Taking new coins with values 5 and 3 doesn't give any fewer coins.
Now suppose you have gotten to the last line, where there are coins with values 1, 9, 5, 3, and 8. During processing, when we get to index 20, working with the coin value of 8, the old W entry is 9 and C entry is 4. Now take 20-8 = 12 and look at the entry under 12: W is 3 and C is 2, so one more coin will give a count of 3, which is an improvement over the old count of 4. So we set W[20] = 8 and C[20] = 3. This means we can get to 20 with 3 coins, namely 8, plus 3 from the entry W[12], plus 9 from the entry W[9]. So 20 = 8+3+9.
Notice that when we started processing the value 5, at the entries for 20 we would have checked the value W[15] = 5 and C[15] = 3. This means that we could get to 20 with 4 coins, namely 20=5+5+9+1, but the count of 4 coins is not better than the 4 coins we already had with 20=9+9+1+1, so these new values don't replace the old. (We could replace them, if we wanted to write the code that way.)

Revision date: 2012-10-29. (Please use ISO 8601, the International Standard.)