0-1無限整数配列のナップザック？

Question

Given an infinite positive integer array or say a stream of positive integers, find out the first five numbers whose sum is twenty.

問題文を読んで、最初0-1 Knapsack問題のようですが、私は0-1 Knapsack algo整数のストリーム上で使用することができる混乱しています。上記の問題の再帰的なプログラムを書くと仮定しましょう。上記関数は無限アレイ上に呼び出すときに現在の要素を無視し続けるであろうように

int knapsack(int sum, int count, int idx) 
{ 
    if (sum == 0 && count == 0) 
     return 1; 

    if ((sum == 0 && count != 0) || (sum != 0 && count == 0)) 
     return 0; 

    if (arr[idx] > 20) //element cann't be included. 
     return knapsack(sum, count idx + 1); 

    return max(knapsack(sum, count, idx +1), knapsack(sum - arr[idx], count -1, idx + 1)); 
} 

次に、すなわちknapsack(sum, count, idx +1)max関数の最初の呼び出しが戻ることはありません。 maxの機能で通話の順序を変更しても、最初の通話は返されない可能性があります。このようなシナリオでknapsack algoを適用する方法はありますか？

Answer 1

これは、正の整数だけで作業している場合に機能します。

基本的に最初の20の数字のいずれかに到達する方法のリストを保持し、新しい番号を処理するたびにこのリストを処理します。

def update(dictlist, num): 
    dk = dictlist.keys() 
    for i in dk: 
     if i+num <=20: 
      for j in dictlist[i]: 
       listlen = len(dictlist[i][j]) + 1 
       if listlen >5: 
        continue 
       if i+num not in dictlist or listlen not in dictlist[i+num]: 
        dictlist[i+num][listlen] = dictlist[i][j]+[num] 
    if num not in dictlist: 
     dictlist[num]= {} 
    dictlist[num][1] = [num] 
    return dictlist 

dictlist = {} 
for x in infinite_integer_stream: 
    dictlist = update(dictlist,x) 
    if 20 in dictlist and 5 in dictlist[20]: 
     print dictlist[20][5] 
     break 

このコードにはマイナーなバグがあり、今はデバッグする時間がありません。しかし、基本的にdictlist [i] [j]は、iと合計するj長さのリストを格納します。

Answer 2

Delphiコード：

var 
    PossibleSums: array[1..4, 0..20] of Integer; 
    Value, i, j: Integer; 
    s: string; 
begin 
    s := ''; 
    for j := 1 to 4 do 
    for i := 0 to 20 do 
     PossibleSums[j, i] := -1; 
    while True do begin 
    Value := 1 + Random(20); // stream emulation 
    Memo1.Lines.Add(IntToStr(Value)); 

    if PossibleSums[4, 20 - Value] <> -1 then begin 
    //we just have found 5th number to make the full sum 
     s := IntToStr(Value); 
     i := 20 - Value; 
     for j := 4 downto 1 do begin 
     //unwind storage chain 
     s := IntToStr(PossibleSums[j, i]) + ' ' + s; 
     i := i - PossibleSums[j, i]; 
     end; 
     Memo1.Lines.Add(s); 
     Break; 
    end; 

    for j := 3 downto 1 do 
     for i := 0 to 20 - Value do 
     if (PossibleSums[j, i] <> -1) and (PossibleSums[j + 1, i + Value] = -1) then 
      PossibleSums[j + 1, i + Value] := Value; 

    if PossibleSums[1, Value] = -1 then 
     PossibleSums[1, Value] := Value; 
    end; 
end; 

出力：

4 
8 
9 
2 
10 
2 
17 
2 
4 2 10 2 2