coin-change with a twist

Question

I am trying to solve a classic dynamic programming coin-change problem with a twist. This is a homework question, I am not looking for full solutions, just for a few pointers to see what I am doing wrong.

Input:

• amount x we want to pay in coins for some value.
• set d representing number of available coins of denominations (1c, 5c, 10c, 25c, 100c, 200c)

Output:

• Minimum number of coins that need to exchange hands for the payment.

Assumptions:

• Cash register operator has unlimited supply of coins and knows how to give optimal change.

What I tried to do so far:

I am trying to build an array C, such that every element C[i], is the /minimum/ number of coins that exchange hands for the amount i.

C[0] = 0

For C[i], I calculate it either by taking minimum of all C[i-di] plus 1, for all available denominations of coins. I then remove the coin I picked from the available coins.

This approach seems to work in simple cases, but when I have, for example:

99 99 0 0 0 1 0

My approach fails, because it's "cheaper" to way $1 which will yield an exchange of 2 coins, than to pay exact 99 cents in cents (exchange of 99 coins).

Any pointers will be appreciated.

Answer 1

It seems like the problem is that you stop when you get to the value you are looking for. If you keep going, figuring out the minimum number of coins to make values larger than x, then add to that the minimum number of coins for the register operator to make proper change, and take the minimum from this larger list, you should be able to answer this.

Edit: You could simplify this slightly if you used two arrays, one for the values you can make and one for the values the register can make. And then you could compare those in some way to get to your answer.

Answer 2

Key points: you can have repetitions for the coins.

Solution: Build an array for which ARR[i] = minimum number of coins to make the value i.

Some pseudocode:

ARR[MAX] = {MAXIMUM VALUE} // set all elements in the array to have some big value
ARR[0] = 0

for C in coins
 for i = 0; i <= needed_value; ++i
   if i+C <= needed_value && ARR[i+C] > ARR[i]+1
     ARR[i+C] = ARR[i]+1

Example:
coins = {1, 3}
needed_value = 8
ARR[] = 0 INF INF INF INF INF INF INF INF
after using the coin with value 3, we will have
ARR[] = 0 INF INF 1 INF INF 2 INF INF
after using the coin with value 1, we will have
ARR[] = 0 1 2 1 2 3 2 3 4
=> we need 4 coins to make the sum