1

我编写的代码使用动态编程解决了基本的硬币找零问题，并给出了找零所需的最小硬币数量。但是我想将每个硬币的数量存储在最小数量中。

我正在尝试做的是初始化一个数组count[]，就像散列一样，它会增加找到的次数coin[j]，min即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]);

}
4

2 回答 2

1

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

当您在内部循环中分配一个新的最小值时，将所有硬币计数复制i - coin[j]到 i 然后递增min_count[i][j]。然后需要的硬币数量为coin_count[value]。

于 2014-05-09T07:41:08.967 回答
0

正如您已经注意到的，自下而上的解决方案每次都添加硬币，不仅是 when i == value，而且如果你想知道硬币的数量 when 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);
};
于 2014-05-09T09:26:16.320 回答