加起来等于一个数字的组合 - Julia lang

Question

我是朱莉娅的新手。有没有一种方法可以将列表中的元素相加，使其达到特定的目标值？我已经使用 Python 的 itertools 库完成了此操作，如下例所示，但我发现对于较大的数据集来说它非常慢。

import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10]
print result  

Answer 1

这被称为背包问题，它没有已知的有效解决方案，这意味着唯一已知的解决方案的时间复杂度会随着数字数量的增加而增加，（NPC）如果您碰巧找到了该问题的有效解决方案，您将赢得一百万美元，因为 P 与 NP 问题是千年问题之一