algorithm - 从一组数字创建 1000、2000 等的总和

Question

好的，问题来了:

我需要从 50-100 个项目集中找到任意数量的中间组，总计 1000、2000、...、10000。

输入:整数列表

整数只能出现在一个列表中。

对算法有什么想法吗？

Answer 1

在谷歌上搜索“背包问题”应该会给您带来不少成功(尽管它们不太可能令人鼓舞——这是一个众所周知的 NP 完全问题)。

编辑:如果您想获得技术知识，您所描述的似乎确实是子集求和问题——这是背包问题的一个特例。当然，这是假设我正确理解了您的描述，我承认这可能会引发一些问题。

您可能会在 The Handbook of Applied Cryptography 中找到算法 3.94有帮助。