找零：动态编程 [英] Coin Change :Dynamic Programming

问题描述

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

The code I have written solves the basic coin change problem using dynamic programming and gives the minimum number of coins required to make the change. But I want to store the count of each coin playing part in the minimum number.

我要做的是初始化数组 count [] ，就像对它进行哈希处理一样，它会增加每当发现分钟时，即 coin [j] ，即 count [coin [j]] + + 。
但这不能按照我想要的方式工作，因为每次找到硬币[j]对应的分钟时，它都会添加硬币。 code>。因此，数字不是最终答案中最终的硬币数量。

What I am trying to do is initializing an array count[] and just like hashing it increments the number of coin[j] whenever min is found, i.e count[coin[j]]++ . But this is not working the way I wanted because it adds the coin every time it finds min corresponding to coin[j]. Hence the number is not the final count of coin in the final answer.

这是代码：

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]);

}

推荐答案

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

You have to keep an extra, two-dinemsional array to store the coin count for each value and each coin denomination.

在内部循环中分配新的最小值时，请复制所有硬币计数从 i-硬币[j] 到i，然后递增 min_count [i] [j] 。然后，所需的硬币数量在 coin_count [value] 中。

When you assign a new minimum in your inner loop, copy all coin counts from i - coin[j] to i and then increment min_count[i][j]. The number of coins needed is then in coin_count[value].

这篇关于找零：动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！