1

我很难弄清楚如何解释这个问题。我目前正在尝试在我的编程课上创建一个额外学分的程序，但我什至不了解它背后的数学......所以如果有人可以帮助我，我会很高兴。好吧：

假设你有 1 美分硬币和 4 美分硬币。并且允许的硬币总数为 4。该值的最大覆盖范围为 11。图表如下。

Value | 1 cent | 4 cent
 1    | 1
 2    | 2
 3    | 3
 4    | 4
 5    | 1      | 1
 6    | 2      | 1
 7    | 3      | 1
 8    |        | 2
 9    | 1      | 2
10    | 2      | 2
11    | Maximum

S0 就是一个例子。我需要为一个更大的数字做这个。但是，如果有人可以帮助我解释数学，我会很高兴。或者等式是什么……这让我发疯了。

我试图实现一个版本的背包算法，但它似乎没有起到作用。如果有人可以提供帮助，将不胜感激。我不确定我是否能够做到这一点，或者我是否需要为此解决方案使用贪心算法。这基本上是贪心算法的一个转折。

编辑：更改为 11

4

2 回答 2

2

动态规划（DP）是解决问题的方法。DP 通常涉及找到一些可以根据该属性的其他值计算的基本属性——一种归纳推理。

在您的情况下，您需要问的基本问题是：“我可以用恰好 k 个硬币赚 n 美分吗”。这是一个简单的布尔值是/否；因为你可以重复使用硬币，你不需要知道如何用硬币制造n美分k，只需要知道是否可能。这隐含地定义了一个布尔矩阵A[n][k]，A[n][k] = TRUE如果你可以用给定种类的硬币赚取n美分。k

研究这个真值表中各个条目之间的关系。例如，如果我可以用 2 个硬币赚 5 美分，那么我可以用 3 个硬币分别赚 6 美分和 9 美分（为什么？）；因此A[5][2]暗示A[6][3]和A[9][3]。

祝你好运！

于 2013-03-12T02:00:46.203 回答
1

注意：我重新发布是因为另一个答案在更新以提供更多上下文时被删除。

如果您想进一步研究，这似乎是原始问题作者和他的 Java 源代码解决方案。

然而，这里是这个算法如何工作的总结，使用动态编程：

假设：
中的 每个值T都受Integer.MAX_VALUE
T约束Integer.MAX_VALUE -1

定义：
D = {d1, d2, ..., dk}∀ d∈ℤ, ∀ w_d = 1
T = W = Total Weight of Knapsack = Total Coins Available for Use

算法的工作原理：

  1. 确保W > 0并通过1 ∈ D
  2. 确保满足上述限制
  3. 创建一个动态大小的数组MinCoins[0] = 0
  4. 让n=1并迭代 1 为n→∞
    • 对于每次迭代，设置MinCoins[ n ] = Integer.MAX_VALUE
    • 迭代Dd中的每个元素，让每个值在迭代期间 被称为
      • 如果d > n跳过此迭代
      • 让z表示此迭代的最佳硬币数量
      • 从上一次迭代中获取最佳硬币数量，然后再添加一个（这个值）：z = MinCoins [ n - d ] + 1
      • z现在比较MinCoins[ n ]
      • 如果z < MinCoins[ n ]找到了新的最优解（保存），否则迭代到下一个d
    • 让为本次迭代找到的最优解定义为q = MinCoins[ n ]
    • 如果q < T则继续下一次迭代。否则，本次迭代没有找到最大解并中断循环。

https://bitbucket.org/asraful/coin-change

于 2016-03-23T03:16:14.020 回答