硬币兑换：动态规划

Question

我编写的代码使用动态规划解决了基本的硬币兑换问题，并给出了进行兑换所需的最小硬币数量。但是我想把每个硬币的数量存储在最小的数字里。

我试图做的是初始化数组count[]，就像散列一样，只要找到min，它就会增加coin[j]的数量，即count[coin[j]。但这并不是我想要的方式，因为它每次发现min对应于coin[j]时都会添加硬币。因此，在最终答案中，数字不是硬币的最终计数。

代码如下：

void makeChange(int coin[], int n, int value)
{
    int i, j;
    int min_coin[MAX];
    int min;

    int count[MAX];
    min_coin[0] = 0;

    for (i=1; i <= value; i++)
    {
            min = 999;
            for (j = 0; j<n; j++)
            {
                    if (coin[j] <= i)
                    {
                            if (min > min_coin[i-coin[j]]+1)
                            {
                                    min = min_coin[i-coin[j]]+1;
                                    count[coin[j]]++;
                            }
                    }
            }
            min_coin[i] = min;
    }

    printf("minimum coins required %d \n", min_coin[value]);

}

Answer 1

正如您已经指出的，自下而上的解决方案每次都会添加硬币，不仅当i==value时，而且如果您想知道i==value时硬币的数量，它取决于子问题的硬币数量，因此我们需要使用二维数组存储以前的计算：

#include <stdio.h>

#define MAX 1000
#define COIN_ARRAY_SIZE 4

void makeChange(int coin[], int n, int value)
{
    int i, j, k;
    int min_coin[MAX];

    int count[MAX + 1][COIN_ARRAY_SIZE] = {0}; // zeroing
    int min;

    //int count[MAX];
    min_coin[0] = 0;

    for (i=1; i <= value; i++)
    {
        min = 999;
        for (j = 0; j<n; j++)
        {
            if (coin[j] <= i)
            {
                if (min > min_coin[i-coin[j]]+1)
                {
                    min = min_coin[i-coin[j]]+1;
                    for(k = 0; k < n; ++k)
                    {
                        count[i][k] = count[i-coin[j]][k]; // copy coin counts when value=i-coin[j]
                    }
                    count[i][j]++; // use a coin[j], increase the count
                }
            }
        }
        min_coin[i] = min;
    }

    printf("minimum coins required %d \n", min_coin[value]);
    for(int i = 0; i < COIN_ARRAY_SIZE; ++i)
        printf("%d: %d\n", coin[i], count[value][i]);

}

测试上述功能的驱动程序：

int main()
{
    int coin[COIN_ARRAY_SIZE] = {5,3,2,1};
    makeChange(coin, 4, 8);
    makeChange(coin, 4, 10);
};

Answer 2

您必须保留一个额外的两位数字数组来存储每个值和每个硬币面额的硬币计数。

当您在内部循环中分配新的最小值时，将所有硬币计数从i-coin[j]复制到i，然后递增min\u count[i][j]。然后，所需的硬币数量在硬币计数[值]中。