0-1 Knapsack trên mảng số nguyên vô hạn?

Question

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

Bằng cách đọc báo cáo vấn đề, đầu tiên nó có vẻ là 0-1 Knapsack vấn đề, nhưng tôi bối rối có thể 0-1 Knapsack algo được sử dụng trên một dòng số nguyên. Giả sử tôi viết một chương trình đệ quy cho vấn đề trên.

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

Bây giờ khi các chức năng trên sẽ kêu gọi một mảng vô hạn, cuộc gọi đầu tiên trong max chức năng ví dụ knapsack(sum, count, idx +1) sẽ không bao giờ trở lại như nó sẽ tiếp tục phớt lờ các yếu tố hiện tại. Ngay cả khi chúng ta thay đổi thứ tự của cuộc gọi trong hàm max, vẫn có khả năng cuộc gọi đầu tiên sẽ không bao giờ trở lại. Có cách nào để áp dụng knapsack algo trong các tình huống như vậy không?

Answer 1

Tính năng này hoạt động nếu bạn chỉ làm việc với các số nguyên dương.

Về cơ bản giữ một danh sách các cách bạn có thể tiếp cận bất kỳ trong số 20 số đầu tiên và bất cứ khi nào bạn xử lý một quy trình số mới danh sách này cho phù hợp.

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 

Mã này có thể có một số lỗi nhỏ và hiện tại tôi không có thời gian để gỡ lỗi. Nhưng về cơ bản dictlist [i] [j] lưu trữ một danh sách dài j mà tổng cho tôi.

Answer 2

mã 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; 

đầu ra:

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