組合算法挑戰

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

夫婦這個例子的組合：

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 

... 

我希望得到一些新的想法，我沒有任何左:)

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）初始化爲[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] - >ÿ

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

答：[0,1,2,5,7] - 溶液

等