如何找到一组中的数字加到另一个给定的数字？

Question

这是一个我似乎在使用会计系统时遇到的问题.

我有一组交易,但它们的金额并不等于会计部门认为应该的金额.他们不会质疑数学,只是包含的交易:p

是否有一种算法可以帮助我确定不应该包含集合中的哪些事务,以使总和与给定量匹配.

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

编辑: 集合中的交易少于100个.有没有人有一个C#的例子,因为解决XKCD问题中的NP完全问题没有一个？

伙计,我应该获得CS学位.

Answer 1

这是子集总和问题,即NP-Complete.但这并不意味着没有找到子集和的算法.

Answer 2

这是背包问题,它是NP-Complete.除了小输入集之外,你不会轻易地解决它.对于任何体面大小的问题集,它都是宇宙生命解决问题的终结之一.

也就是说,那里有遗传算法背包解算器.

Answer 3

正如上面的成员所说,这是子集和问题(或背包问题).然而,要说它不能有效地完成并不是非常精确.它可以完成,而不是在多项式时间内.使用动态编程和递归(以及伪多项式时间),解决方案实际上非常简单.

给定整数[a_1,...,a_n]和数字T,

定义数组S [i,k]以表示a_1,... a_i之间是否存在元素的子集,其中加起来为k.(这是二进制矩阵).

然后我们可以定义一个递归关系,如下所示:

S [i,k] = S [i-1,k]或S [i-1,k-a_j]

换句话说,这意味着我们要么使用元素a_i,要么不使用元素.答案将位于S [n,T].

构造矩阵S的工作量是多少？嗯,S有n*T个元素.要计算每个元素,我们必须做O(1)工作.所以完整的运行时间是O(n*T).

现在在这一点上,似乎我已经证明了P = NP,因为这似乎是一个多项式时间算法.但是,请记住,我们以二进制形式测量输入大小,因此对于某些p,T = 2 ^ p.

我认为没有人会说上述解决方案,如果执行得当,是不合理的.事实上,对于许多合理的问题规模,它将表现令人钦佩.

此外,还有一些启发式方法可以解决这个问题,但我不是该领域的专家.