CODEWITHSUNDEEP
algorithmdynamic-programming
user1500043
user1500043

Reputation: 71

coin-change with a twist

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:

Output:

Assumptions:

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.

Upvotes: 7

Views: 899

Answers (2)

Мартин Радев
Мартин Радев

Reputation: 134

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

Upvotes: 0

Justin
Justin

Reputation: 2372

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.

Upvotes: 1

Related Questions