0-1 Knapsack on infinite integer array?

Question

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?

Answer 1

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.