C++ Return Array/Vector with Minimum Coins to get Value Dynamic Programming

Question

I am tasked with creating a function that takes in an array/vector of coins and a value to be reached. Rather than the function simply returning the minimum number of coins needed, the function must return an array/vector that essentially has the info of how many coins of each denomination should be used such that the least amount of coins are used.

For example, the array coins holds [1, 2, 5, 10] and the desired value is 12 cents. The function should take all of this in and return an array that has the following numbers in it: [0, 1, 0, 1], which denotes that 0 1-cent coins should be used, 1 2-cent coin should be used, 0 5-cent coins should be used, and 1 10-cent coin should be used.

I am using c++ and have to use a dynamic programming algorithm, which I am able to do to just return the minimum number of coins needed. But, I am not sure how to generate the right numbers to fill an array or vector to be returned.

This is what I currently have:

int *minCoins(int coins[], int size, int value)
{
    int *table = new int[value + 1];

    table[0] = 0;

    for (int i = 1; i <= value; i++)
        table[i] = INT_MAX;

    for (int i = 1; i <= value; i++)
    {
        for (int j = 0; j < size; j++)
            if (coins[j] <= i)
            {
                int sub_res = table[i - coins[j]];
                if (sub_res != INT_MAX && sub_res + 1 < table[i])
                    table[i] = sub_res + 1;
            }
    }

    //this is where I am unsure of what to do. should I return table or modify coins somehow?
}

Any help is appreciated!

@Slava my apologies, I was not clear enough on exactly what I am stuck on. I edited my question to hopefully be more clear. It's not whether or not to use an array or vector I am stuck on, I am confused how to generate the right numbers. — J.Einhorn
Then you need to show your effort and where you are stuck at. Currently it looks like you are asking somebody to write your code. — Slava
@J.Einhorn: As Slava has pointed out, you need to show what you've tried so that people can see what the code you're currently stuck at looks like and make concrete suggestions. As it stands right now, this is simply a "Please, do my homework for me"-type of question. — code_dredd
can I talk you out of int *table = new int[value + 1]; and into std::vector<int> table(value+1);? It's a bit sit safer and easier to use. — user4581301

Gassa Gassa · Accepted Answer · 2018-04-17T20:37:10

Instead of storing just the minimum number of coins table[i] for a sum i in a knapsack, we can additionally store the last coin type last[i] that was used to get that table[i]. After that, we can do i -= coins[last[i]] in a loop to get all the coins, until i becomes zero.

In code:

int *minCoins(int coins[], int size, int value)
{
    int *last = new int[value + 1];  // this line added
    int *table = new int[value + 1];
    table[0] = 0;
    for (int i = 1; i <= value; i++)
        table[i] = INT_MAX;

    for (int i = 1; i <= value; i++)
    {
        for (int j = 0; j < size; j++)
            if (coins[j] <= i)
            {
                int sub_res = table[i - coins[j]];
                if (sub_res != INT_MAX && sub_res + 1 < table[i])
                {
                    table[i] = sub_res + 1;
                    last[i] = j;  // this line added
                }
            }
    }

    int *res = new int[size];  // this will be the answer
    for (int i = 0; i < size; i++)
        res[i] = 0;

    int cur = value;  // the value left
    while (cur > 0)
    {
        res[last[cur]] += 1;  // add the current coin
        cur -= coins[last[cur]];  // proceed to the next coin
    }
    delete[] table;
    delete[] last;
    return res;
}

C++ Return Array/Vector with Minimum Coins to get Value Dynamic Programming

2 Answers