如何將算法縮減爲更小的部分以便我可以縮放它？

Question

我已經更新了這個問題（發現最後一個問題還不清楚，如果你想參考它，查看反轉歷史）。目前的答案到目前爲止不起作用，因爲我沒有清楚地解釋我的問題（對不起，第二次嘗試）。

目標：

試圖採取一組數字的（正或負，從而需要邊界限制特定變量的生長），並發現可用於獲得到一個特定的總和它們的線性組合。例如，去利用的總和10 [2,4,5]我們得到：

5*2 + 0*4 + 0*5 = 10 
3*2 + 1*4 + 0*5 = 10 
1*2 + 2*4 + 0*5 = 10 
0*2 + 0*4 + 2*5 = 10 

如何創建一個算法中是可擴展的大量的變量和target_sums？如果給出算法，我可以自己編寫代碼，但如果有庫可用，我可以使用任何庫，但更喜歡使用java。

Answer 1

一個想法是打出來的循環，一旦你設置T[z][i]到true，因爲你只修改基本上這裏T[z][i]，如果它確實成爲true，它永遠不會被再次修改。

for i = 1 to k 
    for z = 0 to sum: 
     for j = z-x_i to 0: 
      if(T[j][i-1]): 
       T[z][i]=true; 
       break; 

EDIT2：另外，如果我得到它的權利，T[z][i]取決於陣列T[z-x_i..0][i-1]上。 T[z+1][i]取決於T[z+1-x_i..0][i-1]。因此，一旦知道T[z][i]是否爲true，則只需檢查一個附加元素（T[z+1-x_i][i-1]）即可知道T[z+1][i-1]是否爲true。

假設您代表T[z][i]是否由變量changed更新。那麼，你可以簡單地說T[z][i] = changed && T[z-1][i]。所以你應該用兩個循環而不是三個來完成。這應該使它快得多。

現在，它的規模 - 現在，T[z,i]只T[z-1,i]和T[z-1-x_i,i-1]依賴，所以填充T[z,i]，你並不需要等待整個(i-1)列被填充到。一旦填入所需的值，您就可以開始使用T[z,i]。我不能在不知道細節的情況下實現它，但是您可以嘗試這種方法。

Answer 2

我認爲這是無限的揹包嗎？完全可以免除c的循環。

for i = 1 to k 
    for z = 0 to sum 
     T[z][i] = z >= x_i cand (T[z - x_i][i - 1] or T[z - x_i][i]) 

Answer 3

根據您所提供的評論部分（有界）（術語的線性組合）和您給我的回答原來的數據。例如，將一個強力的辦法行不通？

c0x0 + c1x1 + c2x2 +...+ cnxn = SUM 

我猜我失去了一些重要的東西，但在這裏它是無論如何：

蠻力分而治之：

• 主控制器爲說，一半係數這些術語（或者很多可能有意義的）
• 然後它將固定係數的每個部分集合發送到工作隊列
• 一名工人拿起一個局部組固定係數，並且進行到蠻力通過剩餘的組合強制我行我素
• 它不會使用太多的記憶力，因爲它的工作順序在每個組有效係數
• 可能是優化忽略等同組合和可能很多其他的方式

爲僞多處理

class Controller 
    work_queue = Queue 
    solution_queue = Queue 
    solution_sets = [] 
    create x number of workers with access to work_queue and solution_queue 
    #say for 2000 terms: 
    for partial_set in coefficient_generator(start_term=0, end_term=999): 
     if worker_available(): #generate just in time 
      push partial set onto work_queue 
     while solution_queue: 
      add any solutions to solution_sets 
     #there is an efficient way to do this type of polling but I forget 

class Worker 
    while true: #actually stops when a stop work token is received 
     get partial_set from the work queue 
     for remaining_set in coefficient_generator(start_term=1000, end_term=1999): 
      combine the two sets (partial_set.extend(remaining_set)) 
      if is_solution(full_set): 
       push full_set onto the solution queue