0-1背包无限整数数组？

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函数中的第一个调用ie 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]存储总和为i的长度列表.