Dynamic Programming Change Problem (Limited Coins). I'm trying to create a program that takes as INPUT:
int coinValues[]; //e.g [coin1,coin2,coin3]
int coinLimit[]; //e.g [2 coin1 available,1 coin2 available,...]
int amount; //the amount we want change for.
OUTPUT:
int DynProg[]; //of size amount+1.
And output should be an Array of size amount+1 of which each cell represents the optimal number of coins we need to give change for the amount of the cell's index.
EXAMPLE: Let's say that we have the cell of Array at index: 5 with a content of 2. This means that in order to give change for the amount of 5(INDEX), you need 2(cell's content) coins (Optimal Solution).
Basically I need exactly the output of the first array of this video(C[p]) . It's exactly the same problem with the big DIFFERENCE of LIMITED COINS. Link to Video.
Note: See the video to understand, ignore the 2nd array of the video, and have in mind that I don't need the combinations, but the DP array, so then I can find which coins to give as change.
Thank you.
Consider the next pseudocode:
for every coin nominal v = coinValues[i]:
loop coinLimit[i] times:
starting with k=0 entry, check for non-zero C[k]:
if C[k]+1 < C[k+v] then
replace C[k+v] with C[k]+1 and set S[k+v]=v
Is it clear?