C++返回具有最小硬币的数组/vector 以获取值(value)动态规划

Question

我的任务是创建一个函数，该函数接受硬币数组/vector 和要达到的值。该函数不是简单地返回所需的最少硬币数量，而是必须返回一个数组/vector ，该数组/vector 实质上包含应使用多少个面额硬币的信息，以便使用最少数量的硬币。

例如，数组 coins 包含 [1, 2, 5, 10] 并且所需的值为 12 美分。该函数应接受所有这些并返回一个数组，其中包含以下数字:[0, 1, 0, 1]，表示 0 1-应使用分硬币，应使用1 2 分硬币，应使用0 5 分硬币，以及1 10 分硬币应该使用硬币。

我使用的是 C++，并且必须使用动态编程算法，我能够做到这一点，只返回所需的最少数量的硬币。但是，我不确定如何生成正确的数字来填充要返回的数组或 vector 。

这是我目前拥有的:

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

感谢任何帮助!

Answer 1

我们可以额外存储最后一个硬币类型 last [i] 用于获取该 table[i]。之后，我们可以循环执行i -= coins[last[i]]来获取所有的硬币，直到i变为零。

在代码中:

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