组合算法挑战

Question

我想解决这个问题已经一个多月了。 我有一个数字和这些变量的列表：

list_num = [1, 1, 2, 3, 5, 6, 1, 1, 3, 4, 4]

#x is number of numbers in combination eg. if x = 5 combiantions will look like this [n,n,n,n,n], where n is possible member of list _num
x = 5
#y is a sum of numbers inside combination
y = 10

我需要生成这些数字的所有可能的组合，因为x是组合中的数字的数目，y是组合中的数字之和，还必须考虑list_num中的重复次数。在

我可以通过生成所有可能的组合来做到这一点，并消除那些不由我的规则决定的组合，但这种方法很混乱，我不能在大量数据中使用它。在我的原始程序中，list_num可以有数百个数字，x和y可以有大的值。在

本例的几个组合：

^{pr2}$

我会很感激一些新的想法，我已经没有了：）

Answer 1

这是一个NP完全问题，请在以下地址找到最佳解决方案：

http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

对于以10为基数的输出数字，您只需对一个变量进行计数，如果符号和是例如10，则进行符号和并输出组合。在

代码：

def SignSum(X):
    Sum = 0

    String = str(X)

    for Sign in String:
       Sum += int(Sign)

    return Sum

Counter = 0


while Counter < 10000:
   if SignSum(Counter) == 10:
      print Counter

   Counter += 1

当然，这也适用于其他具有修改SignSum（）函数的基函数

Answer 3

这里有一个想法：

1）对列表进行排序

2）使用x元素的数组A-这些元素将是索引

3）将A初始化为[0,1,2，…，x-1]

4）现在开始按字典顺序增加索引，例如，首先增加最后一个索引，直到总和达到>；y。然后增加倒数第二个索引，并使最后一个索引为1+倒数第二个索引

等等

第一次迭代：

排序数组：[1，1，1，2，3，3，4，4，5，6]

A:[0,1,2,3,4]

A:[0,1,2,3,5]

A:[0,1,2,3,6]

A:[0,1,2,3,7]

[1,8,1,3]

A:[0,1,2,3,9]

A:[0,1,2,3,10]-溶液

A:[0,1,2,4,5]

A:[0,1,2,4,6]

A:[0,1,2,4,7]

A:[0,1,2,4,8]

A:[0,1,2,4,9]-溶液

A:[0,1,2,4,10]->；y

A:[0,1,2,5,6]

A:[0,1,2,5,7]-溶液

等等