C++ Return Array/Vector 用最小硬币获得价值动态规划

Question

我的任务是创建一个函数，该函数接收 array/vector 个硬币和要达到的值。该函数不是简单地 return 需要的最小硬币数量，而是该函数必须 return 一个 array/vector 本质上具有应该使用多少个面额硬币的信息，以便使用最少的硬币。

例如，数组 coins 包含 [1, 2, 5, 10]，所需的值为 12 美分。该函数应将所有这些都放入 return 一个数组中，其中包含以下数字：[0, 1, 0, 1]，表示应使用 0 1 美分硬币，1 应使用 2 分硬币，0 应使用 5 分硬币，应使用 1 10 分硬币。

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

的数组或向量

这是我目前拥有的：

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

你可以使用 pair dp[i][j] 其中 i 是 1 到 i 索引值 j 的答案然后如果我们使用第 i 个硬币那么 dp[i][j .second = true else false 然后在最后当你达到最小答案时你可以使用递归函数并且对于你达到的每个 dp[i][j] ，如果 bool 为真你必须去 dp[i - 1 ][j - a[i]] 并添加 i 来回答（a 是硬币的价值）否则你必须去 dp[i - 1][j] 什么都不做

dp 更新：

if(dp[i - 1][j].first < dp[i - 1][j - a[i]].first + 1)
{
    dp[i][j].second = false;
    dp[i][j].first = dp[i - 1][j].first;
}
else
{
    dp[i][j].second = true;
    dp[i][j].first = dp[i - 1][j - a[i]].first + 1;
}

递归函数：

void func(int i,int j)
{
    if(i == -1)
       return;
    if(dp[i][j].second)
       ans.push_back(i), func(i - 1,j - a[i]);
    else
       func(i - 1,j);
}

Answer 2

除了在背包中只存储总和 i 的最小数量的硬币 table[i]，我们还可以额外存储用于获得该总和的最后一个硬币类型 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;
}

C++ Return Array/Vector 用最小硬币获得价值动态规划

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

c++

arrays

vector

dynamic-programming

minimum