2

对于硬币找零问题，我们通常有以下递归关系：（P是我们需要找零的总金额，d_i是可用的硬币）

但是我们不能这样：（V是给定的可用硬币的排序集合，i并且j它的下标Vj是给定的最高价值硬币）

C[p,Vi,j] = C[p,Vi,j-1]     if Vj > p
          = C[p-Vj,Vi,j] + 1  if Vj <=p

我写的有什么问题吗？虽然解决方案不是动态的，但它不是更有效吗？

4

2 回答 2

4

考虑P = 6, V = {4, 3, 1}。你会选择4, 1, 1而不是3, 3，所以3硬币而不是最佳的2。

于 2012-10-25T19:11:19.883 回答
0

你写的类似于只在特定条件下工作的贪心算法。（请参阅 -如何判断贪心算法是否足以找到最小硬币变化？）。

另外，在您的版本中，您实际上并没有Vi在重复中使用，所以这只是浪费内存

于 2012-10-25T19:09:31.063 回答