0-1 Knapsack on infinite integer array?

algorithm, dynamic-programming

Solution

This works if you are working with only positive integers.

Basically keep a list of ways you can reach any of the first 20 numbers and whenever you process a new number process this list accordingly.

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

This code might have some minor bugs and I do not have time now to debug it. But basically dictlist[i][j] stores a j length list that sums to i.

Problem

`Given an infinite positive integer array or say a stream of positive integers, find out the first five numbers whose sum is twenty.` By reading the problem statement, it first seems to be `0-1 Knapsack` problem, but I am confused that can `0-1 Knapsack algo` be used on a stream of integers. Let suppose I write a recursive program for the above problem. ``` 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)); } ``` Now when the above function will call on an infinite array, the first call in `max` function i.e. `knapsack(sum, count, idx +1)` will never return as it will keep on ignoring the current element. Even if we change the order of the call in `max` function, there is still possibility that the first call will never return. Is there any way to apply `knapsack` algo in such scenarios?

Original source