5

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

对于给定的美分金额，如果所有硬币管都可以容纳 64 个硬币，则尽量减少硬币管的数量。

每个管只能容纳一种硬币。

每个管子不需要完全填充。

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

6 美分可以作为 6 个 1 美分硬币在一个管中完成，

25 美分可以是一个带有单个 25c 硬币的管子，也可以是一个带有五个 5c 硬币的管子。

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

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

4

3 回答 3

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 个管子中。

于 2012-09-10T08:30:55.340 回答
0

这是一个递归、启发式和贪心算法。

在数组T中，每个都T[i]包含一个由 6 个整数组成的数组。

如果给定的总和是65then 你打电话给tubes(65)then print T[65]。

coins[1..6] = {1, 5, 10, 25, 50, 100}

tubes(sum)
    if sum < coins[1]
        return
    for i = 1 to 6
        tubes(sum - coins[i])
    best-tubes[1..6] = {64, 64, 64, 64, 64, 64}
    for i = 1 to 6
        if sum - coins[i] >= 0
            current-tubes[1..6] = copy of T[sum - coins[i]]
            if current-tubes[i] < 64
                current-tubes[i] += 1
                if current-tubes is better than best-tubes*
                    best-tubes = current-tubes
    T[sum] = best-tubes

为了大大提高运行时间，您可以检查当前T[sum]是否已经过评估。添加此检查完成了称为动态编程的方法。

*current-tubes is better than best-tubes使用更少的管子，或使用相同数量的管子但硬币更少，或使用相同数量的管子，但管子的值更大。这是行动中的贪婪部分。

于 2012-09-10T14:29:11.883 回答
0

像这样的东西：

a[0] = 100; //cents
a[1] = 50; a[2] = 25; a[3] = 10; a[4] = 5; a[5] = 1;

cnt[6]; //array to store how much coins of type i you use;


void rec(sum_left, p /* position in a array */) {
   if ( p == 5 ) {
      cnt[5] = sum_left;
      //count how many tubes are used by cnt array, update current answer if neccessary;
      return;
   }
   for ( int i = 0; i <= sum_left/a[p]; i++ )
      //take i coins of type a[p]
      rec(sum_left - i*a[i], p+1);
}

int main() {
   rec(sum, 0);
}
于 2012-09-10T05:21:39.207 回答