硬币数量有限的最小硬币找零问题

Question

具体来说，问题是：
给定面额数组 coins[]、每个硬币的限制数组 limits[] 和数量 amount、return 需要最少 个硬币，获取 amount，或者如果不可能 return 为 null。另外用解决方案中使用的每个硬币的数量填充数组 change。

这是我的解决方案：

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)
        {
            continue;
        }
        
        for (int i = 0; i < coins.Length; ++i)
        {
            if (coinsUsedToAmount[i, j] >= limits[i])
            {
                continue;
            }
            
            int currAmount = j + coins[i];
            if (currAmount <= amount 
                && (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;
}

但一般情况下是不行的

我的问题是例如在这种情况下：

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] = (9 + 123) // 2 coins

但应该是：

minCoins[132] = (2 + 65 + 35 + 30) // 4 coins

因为这样我就可以使用 9 和 141.

我已经回到这个问题几个星期了，但我仍然无法解决它。我在这个网站和其他网站上看到过许多类似问题的解决方案，但 none 对我有帮助。

Answer 1

我的朋友帮我解决了。我们的想法是，我们从 amount 到 0 并尝试尽可能使用每个硬币的所有名义 - 这样我们就不会在开始时最终使用某些硬币，然后我们就不会'有可能将它们用于金额。

/// <summary>
///  Method used to resolve minimum change coin problem
///  with constraints on the number of coins of each type.
/// </summary>
/// <param name="amount">Amount of change to make, e.g. 13</param>
/// <param name="coins">Available types of coins, e.g. {1, 2, 3, 5}</param>
/// <param name="limits">Number of available coins of specific type, e.g. {1, 5, 3, 2}</param>
/// <param name="change">Number of coins of each type used to make the change, e.g. {0, 0, 1, 2}</param>
/// <returns>
///  Minimal number of coins needed to make the change 
///  (equal to sum of change array entries), e.g. 3
/// </returns>
/// <remarks>
///  coins[i]  - nominal value of the coin of i-th type
///  limits[i] - number of available coins of i-th type (denomination)
///  change[i] - number of coins of i-th type used in the solution
/// 
///  If available `coins` and `limits` does not allow to make provided `amount` of change 
///  then `change` should be set to `null`, and method should also return `null`.
///
///  Tips/requirements:
///   The size of work memory of the algorithm should (must) be 
///   proportional to the value of product: `amount*(coins.Length)` 
///   (that is O(amount*(coins.Length))
/// </remarks>
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];
}

硬币数量有限的最小硬币找零问题

Minimum coin change problem with limited amount of coins

c#

algorithm

dynamic-programming

coin-change