最小硬币找零问题 - 最小公倍数

Question

这个视频涵盖了实现找零最小硬币数的过程。

https://en.wikipedia.org/wiki/Change-making_problem

我不是很清楚的问题在于面试官详细介绍了优化的细节，从这里开始。

https://youtu.be/HWW-jA6YjHk?t=1875

他建议为了得到最小数量的硬币，使用面值为[25,10,1]的方法只需要对50美分以上的找零用算法进行计算，之后我们就能安全地使用25美分。所以如果数额是100.10美元，我们可以一直使用25美分，直到遇到50美分时，此时我们需要使用算法计算精确值。

这对于给定[25,10,1]面值列表是有意义的。要获得他建议的断点数字，可以使用这种情况下的面值的最小公倍数(LCM)，即50。

For example 
32 - 25 * 1 + 1 * 7 = 8 coins. But with 10 cents we can do 
32 - 10 * 3 + 1 * 2 = 5 coins.

因此，我们不能假设 25 美分将被包括在最小硬币数量计算中。

这是我的问题：

假设我们有面额 [25, 10, 5, 1]，它们的最小公倍数仍为 50。但对于任何超过 25 美分且没有包括 25 美分的数量，都不存在最小解。

例如 -

32 - 25 * 1 + 5 * 1 + 1 * 2 = 4 coins. 
32 - 10 * 3 + 1 * 2 = 5 coins

那么在这种情况下，断点不应该是最小公倍数，而应该是25美分，对吗？感谢您的回答。

- Sushant Rao

Answer 1

他们没有说当输入低于断点时不能使用25。他们建议做一个良好的优化是使用最高面额，直到我们将数字降至断点（因为那是保证该部分所需的最少硬币数量），然后切换到更加资源密集型的算法来计算其余所需的硬币。

- גלעד ברקן

---

那部分很清楚，我的问题更具体地是为什么断点不是25，因为在0.25-0.50之间没有任何硬币集，其中25不在最小硬币集中。 - Sushant Rao

@SushantRao 因为在断点下，硬币分配是独特的，取决于给定的目标和面额。面试官定义的“断点”是指我们从简单算法（通过最大面额进行除法）切换到更复杂、动态的程序的点。 - גלעד ברקן

但这并不是独特的，因为在0.25和0.50之间的最小值中始终使用0.25硬币。你能给我一个反例吗？ - Sushant Rao

@SushantRao，您自己举了一个例子，在[25, 10, 1]的情况下，25不在25和50之间使用：32：10 * 3 + 1 * 2 = 5。这就是为什么他们建议在断点处使用动态规划（因为简单的LCM在那里不可靠）。您提出的规则可能适用于特定的面额[25、10、5、1]，但是拥有一个面额集合的规则如何帮助我们一般呢？ - גלעד ברקן

Answer 2

LCM的值为“断点”提供了一个最小的上限，即我们不能轻率地假设最高面额的硬币是解决方案的一部分的那个点。一些数论将证明LCM是一个边界。

50是{25,10}的LCM。对于任何大于等于50的金额，包括至少5*10的任何组合都可以用2*25替换该元素，从而减少硬币数量。这个论点适用于所有其他硬币和它们的组合。这个简单的演示并不普遍适用于LCM以下的情况；会有一些金额作为反例。

为了使整个算法易于理解和维护，我们只使用两个阶段：在断点以上使用最大的硬币，而在断点以下使用完整的DP解决方案——对于大多数应用程序来说，即使是暴力解决方案通常也足够实用。

- Prune