arrays - 总和等于键的数组的最小子集。条件 : Values can be used any number of times

Question

我在面试中被问到这个问题。 给定一个包含“N”个硬币的列表，它们的值在数组 A[] 中，返回求和为“S”所需的最少硬币数量(您可以使用任意数量的硬币)。如果无法求和为“S”，则返回 -1 请注意，我可以多次使用相同的硬币。

示例:

输入#00:

硬币面额:{ 1,3,5 }

所需总和(S):11

输出#00:

3

解释: 最少需要的金币数量是:3 - 5 + 5 + 1 = 11;

除了排序数组并从两端开始之外，我们还有什么更好的方法可以考虑吗？

Answer 1

这是 change-making problem .

您似乎正在考虑的一种简单的贪婪方法并不总是会产生最佳结果。如果你从两端开始详细说明你的意思，我也许能想出一个反例。

它有一个 dynamic programming方法，取自 here :

Let C[m] be the minimum number of coins of denominations d1,d2,...,dk needed to make change for m amount. In the optimal solution to making change for m amount, there must exist some first coin di, where di < m. Furthermore, the remaining coins in the solution must themselves be the optimal solution to making change for m - di.

Thus, if di is the first coin in the optimal solution to making change for m amount, then C[m] = 1 + C[m - di], i.e. one di coin plus C[m - di] coins to optimally make change for m - di amount. We don't know which coin di is the first coin; however, we may check all n such possibilities (subject to the constraint that di < m), and the value of the optimal solution must correspond to the minimum value of 1 + C[m - di], by definition.

Furthermore, when making change for 0, the value of the optimal solution is clearly 0 coins. We thus have the following recurrence.

C[p] = 0                                if p = 0
       min(i: di < p) {1 + C[p - di]}   if p > 0