0-1 अनंत पूर्णांक सरणी पर Knapsack?

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

अब जब ऊपर समारोह एक अनंत सरणी पर फोन करेगा, max समारोह में पहली कॉल अर्थात knapsack(sum, count, idx +1) वापस कभी नहीं होगा के रूप में यह वर्तमान तत्व अनदेखी पर रखेंगे। भले ही हम max फ़ंक्शन में कॉल का ऑर्डर बदल दें, फिर भी संभावना है कि पहली कॉल कभी वापस नहीं आएगी। क्या ऐसे परिदृश्यों में knapsack अलगो लागू करने का कोई तरीका है?

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] एक जे लम्बाई सूची संग्रहीत करता है जो मुझे बताता है।

Answer 2

डेल्फी कोड:

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