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)来满足。

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

解决方案

回答

我们正在寻找硬币找零的问题：

• 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

回答

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

回答

这似乎与子集总和问题密切相关，子集总和问题通常是NP-Complete。

回答

总和= 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，我们就可以停止。

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

回答

我们知道我们现在问了同样完全相同的问题两次。

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

回答

这里给出了一个非常相似的答案：一种算法，用于查找大小为n的列表中的哪个数字求和到另一个数字