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!

Answer 1

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;
}