0-1 Zaino su serie intera infinita?

Question

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

Leggendo la dichiarazione del problema, sembra prima di essere 0-1 Knapsack problema, ma sono confuso che può 0-1 Knapsack algo essere utilizzato su un flusso di numeri interi. Supponiamo di scrivere un programma ricorsivo per il problema precedente.

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)); 
} 

Ora, quando la funzione di cui sopra inviterà un array infinito, la prima chiamata di funzione max cioè knapsack(sum, count, idx +1) sarà mai ritorno, esso continuerà a ignorare l'elemento corrente. Anche se cambiamo l'ordine della chiamata nella funzione max, c'è ancora la possibilità che la prima chiamata non ritorni mai. C'è un modo per applicare knapsack algo in tali scenari?

Answer 1

Questo funziona se si lavora con solo numeri interi positivi.

In pratica, mantenere un elenco di modi in cui è possibile raggiungere uno dei primi 20 numeri e ogni volta che si elabora un nuovo numero, elaborare questo elenco di conseguenza.

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 

Questo codice potrebbe presentare alcuni bug minori e non ho il tempo ora di eseguirne il debug. Ma in pratica dictlist [i] [j] memorizza una lista di lunghezza j che riassume in i.

Answer 2

codice 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; 

uscita:

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