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算法吗？ 最佳答案
如果仅使用正整数，则此方法有效。
基本上保留一个列表，您可以找到前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]存储一个j长度列表，其总和为i。