硬币数量有限的最小硬币更换问题

Question

具体而言，问题是：
给定面额数组<代码>硬币[]，每个硬币的限制数组<代码>限制[]和数量<代码>金额，返回所需的最小硬币数量，以获取<代码>金额，或者如果不可能，返回空值。另外，用溶液中使用的每个硬币的数量填充数组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。

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

Answer 1

我的朋友帮我解决了这个问题。我们的想法是从数量到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];
}