0-1 Mochila en una matriz de enteros infinitos?

Question

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

Al leer el enunciado del problema, en primer lugar, parece ser 0-1 Knapsack problema, pero estoy confundido que puede 0-1 Knapsack algo usarse en una corriente de números enteros. Supongamos que escribo un programa recursivo para el problema anterior.

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

Ahora bien, cuando la función anterior recurrirá a una serie infinita, la primera llamada en función max decir knapsack(sum, count, idx +1) Nunca volveremos ya que mantendrá en ignorar el elemento actual. Incluso si cambiamos el orden de la llamada en la función max, aún existe la posibilidad de que la primera llamada nunca vuelva. ¿Hay alguna forma de aplicar knapsack algo en tales escenarios?

Answer 1

Esto funciona si solo trabaja con enteros positivos.

Básicamente, mantenga una lista de las formas en que puede alcanzar cualquiera de los primeros 20 números y cada vez que procese un nuevo número, procese esta lista en consecuencia.

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 

Este código podría tener algunos errores menores y no tengo tiempo ahora para depurarlo. Pero básicamente dictlist [i] [j] almacena una lista de longitud j que suma a i.

Answer 2

código de 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; 

de salida:

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