我在理解动态编程中的硬币变化问题时遇到了一个小问题。简而言之，我必须使用最少数量的硬币来更改金额。
我有 n 个面额为 1 = v1 < v2 < ... < vn 的硬币，我们记下 M(j) 为金额 j 找零所需的最小硬币数量。
在上面的公式中，我不明白 M(j-vi) 是什么意思。vi 必须是 j-1 中使用的硬币的最大值吗？
2 回答
1
你正在为不同的值 j 制作成堆的硬币，命名为 M(j)。M(j - v i ) 的要点是考虑一个价值为 v i的硬币，那么你将它添加到哪个堆才能达到价值 j？当然，价值 j - v i的那堆硬币加上你现在正在考虑的硬币加起来就是价值 j。
当然，目标是尽可能少的硬币，所以你可以j通过添加一个 v i的硬币来获得最小的堆以达到价值。这就是它的min作用。+1，因为您将硬币 vi 添加到堆中以形成新的堆 M(j) 。
于 2015-01-01T14:11:29.673 回答
0
加一表示您多消费了一枚硬币，因此您所做的总变化会减少所添加硬币的数量，这就是原始 j 值减少的原因。
于 2015-01-01T14:09:58.123 回答