问题标签 [subset-sum]

有谁知道如何从这个伪代码中实现 Java 中的子集和问题？

这真的让我很困惑，所以如果你能添加评论那就太好了！！！

我想知道是否有一种优雅的方法可以将 2n 的所有组合推导出为 n 个非负整数变量的总和。

例如，对于 n = 2 个变量 x 和 y，有 5 个包含两个部分的组合：

x = 0 y = 4；x = 1 y = 3；x = 2 y = 2; x = 3 y = 1；x = 4 y = 0

使得 x + y = 4 = 2n。

更一般地，可以将问题表述为将 s 的所有组合找到 n 个非负整数变量，它们的总和等于 s。

欢迎任何有关如何有效计算此问题的建议，并且非常感谢一些伪代码。谢谢。

编辑：虽然下面在 Perl 和 Prolog 中给出了解决方案，但Java实现可能会带来一个新问题，因为在递归调用期间需要传递和操作数组等线性数据结构，并且这种做法可能会变得非常昂贵，因为 n 得到更大，我想知道是否有针对此问题的替代（和更有效）Java实现。

Given a set A containing n positive integers, how can I find the smallest integer >= 0 that can be obtained using all the elements in the set. Each element can be can be either added or subtracted to the total. Few examples to make this clear.

A = [ 2, 1, 3]

Result = 0 (2 + 1 - 3)

A = [1, 2, 0]

Result = 1 (-1 + 2 + 0)

A = [1, 2, 1, 7, 6]

Result = 1 (1 + 2 - 1 - 7 + 6)

有一个版本的子集问题询问是否有可能找到一组整数的子集，这些整数加起来等于不在子集中的数字的总和。有人知道算法是什么吗？谢谢

我知道这可以通过对数组进行排序并取更大的数字来完成，直到满足所需的条件。这至少需要 nlog(n) 排序时间。

有没有改善nlog(n)。

我们可以假设所有数字都是正数。

最近我开始对子集和问题感兴趣，该问题是在超集中找到一个零和子集。我在 SO 上找到了一些解决方案，此外，我遇到了一个使用动态编程方法的特定解决方案。我根据他的定性描述用 python 翻译了他的解决方案。我正在尝试针对占用大量内存的较大列表进行优化。有人可以推荐优化或其他技术来解决这个特定问题吗？这是我在 python 中的尝试：

我必须做一个使用遗传算法解决子集和问题的项目。不幸的是，在编写算法时我发现了一个大问题......

我的算法：

• 只要没有找到解决方案并且步骤数小于步骤数：
• 计算每个染色体的概率然后分布函数
• 执行选择（轮盘赌）
• 选择n条染色体进行杂交
• 执行交叉（交叉点随机选择）
• 选择 m 条染色体进行突变
• 执行突变
• 如果您找到了解决方案，请停止

（算法取自《遗传算法 + 数据结构 = 进化程序，第 2 章》一书） 种群规模、数据量、数据收集范围、步数、突变数（步内）、在程序选项中严格设置交叉次数（在一个步骤中）。

问题在于，在种群中经过一定（相对较少）的步骤后，所有染色体都是相同的。问题说明了这个图表：http: //imageshack.us/m/96/7693/wykresb.png

我做错了什么？如何解决？提前致谢。

编辑：

在这里你可以找到我的应用程序的日志：http: //paste.pocoo.org/show/391318/

我认为轮盘赌不是最好的解决方案（正如 deong 所说）。突变也需要改进。

给定一组整数，如何找到总和为给定值的子集......子集问题？

示例： S = {1,2,4,3,2,5} 和 n= 7 查找总和为 n 的可能子集。我试图用谷歌搜索发现很多链接，但不清楚。我们如何在 java 中解决这个问题，要使用的数据结构及其复杂性是什么？

我一直在努力应对 Greplin 挑战的第 3 级。对于那些不熟悉的人，这里是问题：

您必须找到数组的所有子集，其中最大数字是剩余数字的总和。例如，对于以下输入：

(1, 2, 3, 4, 6)

子集将是

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

这是您应该在其上运行代码的数字列表。密码是子集的数量。在上述情况下，答案是 4。

3、4、9、14、15、19、28、37、47、50、54、56、59、61、70、73、78、81、92、95、97、99

我能够编写一个解决方案，构建所有 400 万个以上 22 个数字的组合，然后对它们进行测试，这将使我得到正确的答案。问题是它需要 40 多分钟才能完成。在网上搜索，似乎有几个人能够编写一个算法来在不到一秒钟的时间内得到答案。任何人都可以用伪代码解释比计算昂贵的蛮力方法更好的方法来解决这个问题吗？快把我逼疯了！

我有一个现实世界的问题（不是家庭作业！），需要找到集合 A 的子集的总和，它等于其他集合 B 的子集的总和。

一个非常相似的问题有一个有用的答案是here。

考虑这个例子：

使用该问题的已接受答案中提供的代码，我得到以下输出：

出于我的目的，我只想要使用输入集中元素最少的答案。在这个例子中，我只想

因为所有其他答案也有200和4000。也就是说，我正在寻找“最简单”的可能总和（从某种意义上说，它们使用最少的元素）。有人可以提出一种合理有效的方法吗？（蛮力是可以的，因为我的阵列不是那么大。）

另外，我应该注意输出的第二行sum(200 4000 4000) ..., 是不正确的，因为4000只在@a. 恐怕我对算法的理解不够深入，无法理解为什么会发生这种情况。

任何对其中任何一个的帮助将不胜感激！