有限硬币的最小找零问题

Question

具体来说，问题是：
给定面值数组coins[]、每种硬币的限制数组limits[]和数字amount，返回获取amount所需的最小硬币数，如果不可能，则返回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。

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

- Mr Patience

Answer 1

我的朋友帮我解决了这个问题。思路是从 amount 到 0 逐渐使用每个硬币的面额 - 这样我们就不会在开始时使用某些硬币，然后无法将它们用于amount。

/// <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];
}

- Mr Patience

---

这个例子能用吗？我检查了但是没有得到答案。 - Himashi Rodrigo

@HimashiRodrigo，是的，它应该可以工作-我刚才检查过了（在提供的示例上）。如果有帮助，我还添加了一些文档。 - Mr Patience