0

可能重复：
查找列表中哪个数字总和等于某个数字的算法

问题：

有一个列表：[1,2,3,4,6,8,10,12]，我想用这些数字总结一个新的数字 16。

规则：

1）不需要使用所有的数字，6 + 10 就可以了。

2）一个数字可以多次使用，12+2+1+1就可以了。

3）顺序很重要，12+6和6+12是两种不同的组合。

我已经看到算法来总结所有组合的数字列表，但这不一样。

对算法不太了解，如果这适合某些算法，请告诉我，或者一些python代码/伪代码将不胜感激。

4

1 回答 1

4

首先 - 请注意，即使找到总和为所需数字的任何子集也是NP-Complete并且被称为子集和问题，因此没有已知的多项式解决方案。

现在，关于具体问题，这里有一些选项：

首先当然有明显的“生成所有子集并检查总和”的方式。请注意，如果您的元素都是非负的，您可以在实际开发它们之前使用分支和绑定并终止大部分可能性（如果您找到了一个子集X，sum(X) == s并且您正在寻找数字n < s- 您可以确定任何包含的集合X都不会找到解决方案）。类似于以下内容：

findSubsets(list,sol,n):
  if (list.empty() and n == 0): #found a feasible subset!
     print sol 
     return
  else if (n < 0): #bounding non feasible solutions
     return 
  else if (list.empty()): #a solution that sums to a smaller number then n
     return
  e <- list.removeAndReturnFirst()
  sol <- sol.add(e)
  findSubsets(list,sol,n-e)
  sol <- sol.removeLast()
  findSubsets(list,sol,n)
  list.addFirst(e) #cleanup, return the list to original state

调用findSubsets(list,[],n)wherelist是您的项目列表，n是所需的数字并且[]是一个空列表。

请注意，如果需要，它可以很容易地并行化，在探索的两个子集之间不需要真正的同步。

如果列表仅包含整数，则另一种选择是使用动态编程来解决子集和问题。获得矩阵后，您可以通过返回表格重新创建表格中的所有元素。这个类似的问题讨论了如何从背包 DP 解决方案中获取列表。这两个问题的原理几乎相同。

于 2012-12-05T07:53:13.873 回答