發現，加起來數量X

正數的列表中的所有元素我試圖反向工程遺留報告，並使用Python來解決問題。發現，加起來數量X

傳統報告有20萬的結束和數量。

我知道怎麼會落得這個200K的數字集合，但是這個集合中充斥着那些被過濾掉（與邏輯我還沒有明白的）許多其他的數字。我怎麼能遍歷數字列表來找到所有可變長度的條目（子列表）（可能是1個元素= 200k，或15個元素的產品...），這將添加高達200k？

我開始寫出來，然後決定尋求幫助時，我意識到元素＃1 + 2可能溢出，但列表元素＃1 + 4 + 7可能是比賽進行到20萬....

這幾乎就像因式分解，然而用總和而不是產品，並且在可能的候選人列表中。

不知道。有任何想法嗎？任何人都做過這樣的事情？

其他細節：
隨着置換和numpy的我得到的結果符合市場預期，但它走的時間太長了與預期的輸入和輸出。（？即天..）

下面

就是我在：

下面似乎給出正確的結果，但現在看來，這將需要一段時間。

我會接受上面的答案，讓這個在夜間運行。

感謝，

from itertools import permutations 
import numpy , pickle, random 
output_results = {} 
input_array = [random.randrange(0,15000) for i in range(1000)] 
desired_sum = 200000 
#input_array = (1,2,9,13,12) 
#desired_sum = 23 

for r in range(1,len(input_array)): 
    for p in permutations(input_array, r): 
     temp_sum = numpy.sum(p) 
     if temp_sum == desired_sum: 
      output_results[p] = numpy.sum(p) 
    if r % 10 == 0: 
     print "Finished up to number %s " % r 

pickle.dump(output_results, open("save.p", "wb"))

來源

2013-02-04 joefromct

這就是揹包概率LEM。 –

我可以給你[這]（https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p）鏈接，但是這將是像欺騙你的功課。 – danodonovan

這是子集和問題，而不是揹包問題。 – interjay

Itertools.permutations可以提供幫助。

變r值在permutations(iterable, r)你可以嘗試找到含有從iterable（您的收藏）r項所有可能的排列，其中您可以輕鬆地獲得資金（例如用numpy.sum）。

如果你有什麼樣的期待，並設置一個合理的上限r你應該得到的答案在合理的時間

編輯

@joefromct一些想法：你可以先估計最大找到在下面的方式，你想要的解決方案所需r值（未測試，但這個想法應該是正確的）

sorted_input = np.sorted(input_array) 
cumsum = np.cumsum(sorted_input) 
max_r = (cumsum<desired_sum).sum() 
if max_r == len(input_array) and sorted_input[-1] < desired_sum: 
    print("sorry I can't do anything for you") 
    exit() 

for r in range(1,max_r): 
    [...]

來源

2013-02-04 17:40:22

鑑於提及15個數字作爲樣本，我預計蠻力會太慢。 –

隨着排列和numpy.sum我確實有東西給我適當的輸出，但它需要相當長的時間來循環通過更大的結果... – joefromct

Francesco Montesano上面的答案做了伎倆，但與問題是NP完全HTTP ：//en.wikipedia.org/wiki/NP-complete它跑了幾個小時，然後提出我的正確答案。 – joefromct

發現，加起來數量X

回答

相關問題