算法來確定列表中的哪些數字是給定數字的總和

Question

我有一個編碼問題，我嘗試解決。我還沒有能夠提出一個好的算法呢。

給定數字X（例如200），確定當列表中的哪些數字（例如：4,5,10,10,23,67,889,150,50）總和時將等於X.在此如果答案是（50,150）。到目前爲止，我首先考慮了對列表進行排序（從最低到最高），然後循環添加數字，直到獲得大於X的值。由於不需要（例如889），因此放棄列表中所有剩餘的數字。現在我有產生總數爲200所需的數字列表。現在我需要確定哪些是總計爲200的數字。

目前卡在這一點。

非常感謝任何想法。

Answer 1

這是一個揹包問題。這裏請參考https://en.m.wikipedia.org/wiki/Knapsack_problem

Answer 2

唯一可以丟棄的數字是大於目標數字的數字，因爲任何其他小數字的組合可能總計達到期望的數量。

要找到哪些（如果有的話），你將不得不檢查剩餘數字的所有可能的組合。

最簡單的方法是遞歸遍歷列表，一旦添加了當前數字，並且一旦將其刪除，修剪當前分支（如果總和已經超過目標值）。

一個例子（perl的）實現您的問題例如在下面的代碼片段給出：

my @numbers = (4, 5, 10, 10, 23, 67, 889, 150, 50); 
my $length = scalar @numbers; # length of the list 


sub visit { 
    my ($i, $sum, $goal, $items) = @_; 
    # i: current index, sum: sum of numbers currently selected 
    # goal: goal value to reach, items: list of numbers currently selected 

    # we found a solution ! 
    print join (", ", @$items) . "\n" if $sum == $goal; 

    return if $i >= $length || $sum >= $goal; 

    # continue without adding 
    visit ($i+1, $sum, $goal, $items); 

    # continue with adding 
    visit ($i+1, $sum + $numbers[$i], $goal, [$numbers[$i], @$items]); 
} 

visit (0, 0, 200, []);它將報告對50, 150預期。

注意，沒有試圖刪除重複製成，具有77 visit (0, 0, 77, []);的目標值除了三重50, 23, 4對67, 10會列出兩次因此調用，因爲也有10那兒兩個實例。

哦，不要相信任何在其他帖子中提出的貪婪算法，因爲它們註定會失敗解決揹包問題。

Answer 3

取決於。如果你想讓它快，你可以用一個貪婪（ISH）算法：（僞代碼）

n = answer; // what you want the numbers to add up to be. 
numbers = [1, 2, 40, 39,....]; //the candidates. 
addList = Array[][]; 
addList[0] = numbers; 
level = 0; 
while(true){ 
    for (number in numbers){ 
     currnum = addlist[level][i] + number; 
     if(currnum == n){ 
      return true; // or what ever you want to return 
     } else if (currnum < n){ 
       addlist[level+1].append(currnum); 
     } 
    } 
    if (addlist[level+1].length ==0){ 
      return false; // it will never add up to the value n. 
    } 
    level++; 
} 

這是嚴格僞代碼，我混合ArrayList和數組有點只是可讀性。