c++ - 寻找最小编号。可以用来给 x 找零的面额

Question

变体1：

如果在硬币找零问题中，您必须找出可用于为输入 X 提供找零的最小面额数。我理解 Greedy & DP 方法。

1. 尝试所有可能的大小 r 组合（ r=1 到 n ），看看哪一个有效。
2. 创建一个维度为 (x+1) xn 的矩阵并使用 DP。

我正在考虑一个递归解决方案，对于每个面额d[i]，我将在d[i]排除时递归调用 min_cur 函数，并且至少d[i]包含 of 时，从两个中选择最小值。

for all i range of d[0] to d[n]

min_cur( x -> (d[1], d[2], …, d[n]) ) = 
    minimum( min_cur(  x    -> (d[1], d[2], …, d[n] excluding d[i]) ), 
             min_cur( (x-i) -> (d[1], d[2], …, d[n]) ).

但这个递归总是给出答案为 1。

它需要一些改进。我不确定如何改进它。另外，如果您还想打印所有使用的面额怎么办？

变体2：

与上述相同的问题，但每个面额的硬币数量有限 - 即对于d[i]，您最多可以使用l[i]硬币。这有最优的子结构吗？我不确定，因为子问题相互依赖。对此最好的贪婪方法是什么？

标签： c++algorithmdynamic-programminggreedycoin-change