有什么好的算法来判断是否可以从一组数字中累加建立通过量？

Possible Duplicate:
Algorithm to find which numbers from a list of size n sum to another number

有什么好的算法来判断是否可以从一组数字中累加建立通过量？ 就我而言，我正在确定是否可以通过将一组账单(例如5美元，10美元和20美元)相加来满足一定的货币金额(例如40美元)。 这是一个简单的示例，但是该算法需要适用于一般情况，在这种情况下，账单集可能会随时间变化(由于用完了账单)或由于面额不同的货币而有所不同。 该问题将适用于机场的外汇出纳员。

因此，$ 50可以用一组($ 20和$ 30)来满足，而不能用一组($ 20和$ 40)来满足。

此外。 如果可用可用的面额无法满足该金额，您如何确定可以满足的最高和最低金额？

---

这似乎与子集和问题密切相关，而子集和问题通常是NP完成的。

---

您正在寻找硬币找零的问题：

• http://en.wikipedia.org/wiki/Coin_problem

• http://www.egr.unlv.edu/~jjtse/CS477/DP%20Coin%20Change.html

• http://www.algorithmist.com/index.php/Coin_Change

---

您知道-您两次问了同样的问题。

有什么好的非递归算法来确定是否可以从一组数字中累加构建通过量？

---

总和= 100
账单=(40,30,20,10)

40的个数= 100/40 = 2
剩余= 100％40 = 20

30的数量= 20/30 = 0
剩余= 20％30 = 20

20的数量= 20/20 = 1
剩余= 20％20 = 0

一旦余数= 0，就可以停止。

如果您用完了钞票，则无法弥补，需要转到第二部分，即可以得到多近的距离。这是一个可以用线性代数方法解决的最小化问题(对此我有些生疏)

---

从最大的账单开始，然后逐步减少。对于每种面额，请从数量最多的这些钞票开始，然后逐步减少。您可能需要较少的大面额，因为您需要多个较小的面额才能达到目标。

---