algorithm - 对于给定的 cent 数量，如果所有管都装有 64 但不需要填充，则最小化硬币管的数量

Question

编辑:如果有人可以为著名的硬币找零问题提供一个解释性的递归答案(一个链接就可以)，这将有很大帮助

---

对于给定的分值，如果所有硬币管都能容纳 64 个硬币，则尽量减少硬币管的数量。

每个 pipe 只能装一种硬币。

每个 pipe 不需要装满。

---

例如对于美国硬币，金额为 0.01 美元、0.05 美元、0.10 美元、0.25 美元、0.50 美元和 1.00 美元

6 美分可以像 6 个 1 美分硬币一样装在一个 pipe 里，

25 美分可以是装有一枚 25 分硬币的 pipe ，也可以是装有五枚 5 分硬币的 pipe 。

65 美分将作为 13 个 5c 硬币完成，因为 65 个 1c 硬币需要使用 2 个 pipe 。

---

我正在尝试编写一个 minecraft 插件，但我在使用该算法时遇到了很多困难。

Answer 1

查找表是一个很好的方法。

int[] Coins = new[] { 100, 50, 25, 10, 5, 1 };
int[,] Table = new int[6,6400];

/// Calculate the number of coins of each type that minimizes the number of
/// tubes used.
int[] Tubes(int cents)
{
    int[] counts = new int[Coins.Length];
    if (cents >= 6400)
    {
        counts[0] += (cents / 6400) * 64; // number of coins in filled $1-tubes
        cents %= 6400;
    }
    for (int i = 0; i < Coins.Length; i++)
    {
        int count = Table[i, cents]; // N coins in (N + 63) / 64 tubes
        counts[i] += count;
        cents -= count * Coins[i];
    }
    return cents;
}

要计算表格，您可以使用:

void CalculateTable()
{
    for (int i = Coins.Length-1; i >= 0; i--)
    {
        int coin = Coins[i];
        for (int cents = 0; cents < 6400; cents++)
        {
            if (i == Coins.Length-1)
            {
                // The 1 cent coin can't be divided further
                Table[i,cents] = cents;
            }
            else
            {
                // Find the count that minimizes the number of tubes.
                int n = cents / coin;
                int bestTubes = -1;
                int bestCount = 0;
                for (int count = cents / coin; count >= 0; count--)
                {
                    int cents1 = cents - count * coin;
                    int tubes = (count + 63) / 64;
                    // Use the algorithm from Tubes() above, to optimize the
                    // lesser coins.
                    for (int j = i+1; j < Coins.Length; j++)
                    {
                        int count1 = Table[j, cents1];
                        cents1 -= count1 * Coins[j];
                        tubes += (count1 + 63) / 64;
                    }
                    if (bestTubes == -1 || tubes < bestTubes)
                    {
                        bestTubes = tubes;
                        bestCount = count;
                    }
                }
                // Store the result
                Table[i,cents] = bestCount;
            }
        }
    }
}

CalculateTable 在几毫秒内运行，因此您不必将其存储到磁盘。

示例:

Tubes(3149)  -> [ 31,  0,  0,  0,  0, 49]
Tubes (3150)  -> [  0, 63,  0,  0,  0,  0]
Tubes (31500) -> [315,  0,  0,  0,  0,  0]

数字表示硬币的数量。 N 个硬币可以放入 (N + 63)/64 个 pipe 中。