0

我试图解决这个问题一个多月了。我有一个数字列表和这些变量：

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可以有很大的值。

此示例的几个组合：

comb1 = [1,1,2,3,3], x = 5, y = 10
comb2 = [1,1,1,2,5], x = 5, y = 10
comb3 = [1,1,1,1,6], x = 5, y = 10

...

我会很感激一些新的想法，我没有任何剩余:)

4

3 回答 3

3

这是一个想法：

1) 对列表进行排序

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

3) 将 A 初始化为 [0,1,2,...,x-1]

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

等等

前几次迭代：

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

答：[0,1,2,3,4]

答：[0,1,2,3,5]

答：[0,1,2,3,6]

答：[0,1,2,3,7]

答：[0,1,2,3,8]

答：[0,1,2,3,9]

答：[0,1,2,3,10] - 解决方案

答：[0,1,2,4,5]

答：[0,1,2,4,6]

答：[0,1,2,4,7]

答：[0,1,2,4,8]

答：[0,1,2,4,9] - 解决方案

答：[0,1,2,4,10] - >y

答：[0,1,2,5,6]

答：[0,1,2,5,7] - 解决方案

等等

于 2013-04-08T09:18:50.750 回答
1

这是 NP 完全问题，请在以下位置找到最佳解决方案：

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

于 2013-04-08T10:48:38.127 回答
0

对于以 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() 函数的其他基础

于 2013-04-08T09:14:24.230 回答