硬币数量有限时的最小硬币找零问题 [英] Minimum coin change problem with limited amount of coins

问题描述

具体来说，问题是:
给定面额数组 coins [] ，每个硬币的限额数组 limits [] 和数字 amount ，返回最小值要获得 amount 所需的硬币数量，如果不可能，则返回null.此外，在数组 change 中填写解决方案中使用的每种硬币的编号.

这是我的解决方案:

To be specific, the problem is:
Given array of denominations coins[], array of limit for each coins limits[] and number amount, return minimum number of coins needed, to get the amount, or if it's not possible return null. Additionally fill array change with number of each coin used in the solution.

This is my solution:

public static int? Dynamic(int amount, int[] coins, int[] limits, out int[] change)
    {
        int[] minCoins = new int[amount + 1];
        int[,] coinsUsedToAmount = new int[coins.Length, amount + 1];

        minCoins[0] = 1;
        for (int j = 0; j < amount; ++j)
        {
            if (minCoins[j] > 0)
            {
                for (int i = 0; i < coins.Length; ++i)
                {
                    if (coinsUsedToAmount[i, j] < limits[i])
                    {
                        int currAmount = j + coins[i];
                        if (currAmount <= amount)
                        {
                            if (minCoins[currAmount] == 0 || minCoins[currAmount] > minCoins[j] + 1)
                            {
                                minCoins[currAmount] = minCoins[j] + 1;

                                for (int k = 0; k < coins.Length; ++k) 
                                {
                                    coinsUsedToAmount[k, currAmount] = coinsUsedToAmount[k, j];
                                }
                                coinsUsedToAmount[i, currAmount] += 1;
                            }
                        }
                    }
                }
            }
        }

        if (minCoins[amount] == 0)
        {
            change = null;
            return null;
        }

        change = new int[coins.Length];
        for(int i = 0; i < coins.Length; ++i)
        {
            change[i] = coinsUsedToAmount[i, amount];
        }

        return minCoins[amount] - 1;
    }

但是它通常无法正常工作.

But it doesn't work in general.

我的问题是例如:

amount = 141, 
coins = new int[] { 2, 137, 65, 35, 30, 9, 123, 81, 71 }                                                                                  
limits = new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1 }

最佳解决方案是:

 change = new int[] { 1, 0, 1, 1, 1, 1, 0, 0, 0 }

我的算法给出的结果为null.换句话说，它失败了，每当在某种程度上，我将不得不使用比可能的情况少的最优解决方案，然后，最后，我不需要硬币.
在此示例中，我的算法给出:
minCoins [132] = 2(9 + 123)，
但这应该是 minCoins [132] = 4(2 + 65 + 35 + 30)，因为这样我就可以使用 9 并具有 141

And my algorithm gives null as a result. In the other words it fails, whenever on some way up I would have to use less optimal solution than it's possible, and then, at the end, I don't have needed coins.
In this example my algorithm gives:
minCoins[132] = 2 (9 + 123),
But it should be minCoins[132] = 4 (2 + 65 + 35 + 30), because then I can use 9 and have 141.

我已经回到这个问题了几周了，但仍然无法解决:(我确实在该站点和其他站点上看到了许多解决类似问题的解决方案，但是没有一个对我有帮助.

I have been coming back to this problem for a few weeks now and still can't solve it :( I had really seen numerous solutions to similar problems on this and other sites, but none helped me.

推荐答案

我的朋友帮助我解决了这个问题.想法是，我们将 amount 更改为 0 ，并尝试尽可能使用每种硬币的名义价值-这样一来，我们最终就不会使用某些硬币了.开始，然后我们将无法使用它们作为金额.

Friend of mine helped me solve it. The idea is that we go from the amount to 0 and try to use all the nominal of each coins possible - that way we won't end up using certain coins at the beginning, and then we wouldn't have possibility to use them for amount.

public static int? Dynamic(int amount, int[] coins, int[] limits, out int[] change)
{
        int[][] coinsUsed = new int[amount + 1][];
        for (int i = 0; i <= amount; ++i)
        {
            coinsUsed[i] = new int[coins.Length];
        }

        int[] minCoins = new int[amount + 1];
        for (int i = 1; i <= amount; ++i)
        {
            minCoins[i] = int.MaxValue - 1;
        }

        int[] limitsCopy = new int[limits.Length];
        limits.CopyTo(limitsCopy, 0);

        for (int i = 0; i < coins.Length; ++i)
        {
            while (limitsCopy[i] > 0)
            {
                for (int j = amount; j >= 0; --j)
                {
                    int currAmount = j + coins[i];
                    if (currAmount <= amount)
                    {
                        if (minCoins[currAmount] > minCoins[j] + 1)
                        {
                            minCoins[currAmount] = minCoins[j] + 1;

                            coinsUsed[j].CopyTo(coinsUsed[currAmount], 0);
                            coinsUsed[currAmount][i] += 1;
                        }
                    }
                }

                limitsCopy[i] -= 1;
            }
        }

        if (minCoins[amount] == int.MaxValue - 1)
        {
            change = null;
            return null;
        }

        change = coinsUsed[amount];
        return minCoins[amount];
}

这篇关于硬币数量有限时的最小硬币找零问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！