Dynamic Programming Coin Change Limited Coins

Question

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.

Answer 1

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?