问题标签 [subset-sum]

这是一道面试题：

4 个人 - 每人可以在 1、3、7 和 10 分钟内过桥。一次只能两个人走桥。他们过桥需要多少分钟？

我可以手动想到一个解决方案：10 和 7 在一起，一旦 7 到达目的地，“3”跳进去，10 和 3 一起完成。现在 1 自行消失，总时间为 11。因此，{10, 7} 后跟 {10, 3} 后跟 {1}。

我无法考虑如何将其实现为通用算法的代码。有人可以帮我确定如何将这个想法转换为一些真实的代码吗？

子集和问题以 NP 完全而闻名，但是有各种技巧可以快速解决问题的版本。

通常的动态规划算法需要随目标总和增长的空间。我的问题是：我们可以减少这个空间需求吗？

我正在尝试解决具有少量元素但目标和非常大的子集和问题。元素的数量对于指数时间算法（和快捷方法）来说太大了，对于通常的动态规划方法来说目标和太大。

考虑这个说明问题的玩具问题。给定集合A = [2, 3, 6, 8]，找出总和为 的子集的数量target = 11。枚举所有子集我们看到的答案是 2:(3, 8)和(2, 3, 6)。

当然，动态编程解决方案给出了相同的结果 -ways[11]返回2：

target = 1100现在考虑以set的总和为目标A = [200, 300, 600, 800]。显然仍然有 2 个解决方案：(300, 800)和(200, 300, 600). 但是，该ways阵列增长了 100 倍。

填写动态编程存储数组时是否可以跳过某些权重？对于我的示例问题，我可以计算输入集的最大公分母，然后将所有项目减少该常数，但这不适用于我的实际应用程序。

这个 SO question是相关的，但这些答案没有使用我想到的方法。Akshay在此页面上的第二条评论说：

...在 n 非常小（例如 6）且总和非常大（例如 100 万）的情况下，空间复杂度将太大。为了避免大的空间复杂度，可以使用 n HASHTABLES。

这似乎更接近我正在寻找的东西，但我似乎无法真正实现这个想法。这真的可能吗？

编辑添加：要解决的问题的较小示例。有1个解决方案。

一个真正的问题是：

我正在尝试将“列出字符串中的所有组合”问题修改为我们需要打印具有给定“总和”的所有集合的问题。这是我的初始代码，但我不确定如何在代码中保存集合列表：

我们如何修改此代码以使其打印具有总和“总和”的所有可能集合。谢谢！

我正在尝试建立一个问题，以解决另一个类似的问题...下面给出的是用于查找总和为特定值的子集总数的代码，我正在尝试修改代码以便我可以返回所有总和为该值的子集（而不是找到计数）。

查找总和为“sum”的 suibset 总数的代码：

有人可以对此代码提出一些更改，使其返回子集而不是子集计数吗？

我想做的事

我想找到总和为 target 的数组的子集T。我还想使用动态编程方法（以及自下而上的解决方案）来做到这一点。

我目前拥有的

目前，我只找到了一种方法来查看是否在 size 的所有子集中N，是否至少有一个子集具有所需的总和。请参阅下面的代码。

我被困在哪里

现在，我知道是否有解决方案，但我想不出一种方法来实际输出解决方案。

我不是在寻找任何人为我提供特定代码，但欢迎使用伪代码以及如何保存解决方案的提示。

我在 wiki http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution上阅读了关于 sumsubsetproblem 的内容，并想知道我是否可以将其调整为以下问题：

我需要所有可能的子集 ss1, ss2 受 n1 限制，n2 是 2 个集合 s1,s2 中的元素数

我将使用 S1 的元素作为正元素，使用 s2 的元素作为负元素来回答大小为 n1 和 n2 的子集总和是否等于 0 的问题

我在这里的特殊问题是集合可以包含 0 本身，我想我可以通过将这些元素设置为 1 或 -1 来解决这个问题（ 1 不是我输入的成员，它将是 (0,10,50,100,200,500) ）和下一个问题是这个算法只给了我是或否，但我已经知道这个答案（它的前提条件）我需要的是结果。

这还不够快吗？我在这里读过一个 perl 实现，其中 OP 发布了一个包含运行时的列表，一个 30 个元素的计算时间为 30-40 秒，这对于我的需求来说太慢了，我需要在 java 中实现，目前为止据我所知，甚至比 perl 还要慢

问候

短剑

我想计算集合 S 中存在多少对不相交的子集 S1 和 S2（S1 U S2 可能不是 S），其中 S1 中的元素总和 = S2 中的元素总和。

假设我已经计算了所有可能的 2^n 子集的所有子集总和。我如何找到有多少不相交的子集具有相等的总和。

对于总和值 A，我们可以使用总和 A/2 的子集计数来解决这个问题吗？

例如：S ={1,2,3,4}

可能的各种 S1 和 S2 集是：

S1 = {1,2} 和 S2 = {3}

S1 = {1,3} 和 S2 = {4}

S1 = {1,4} nd S2 = {2,3}

这是问题的链接： http ://www.usaco.org/index.php?page=viewproblem2&cpid=139

假设我们有一套

目标是找到我们通过以下方式创建的总和：我们找到长度为 3 的所有子集，然后将每个子集的元素相乘（对于子集{b_1, b_2, b_3}，结果将为b_1*b_2*b_3）。最后我们总结了所有这些产品。

我正在寻找一种最短时间执行算法。

例子

我有一个函数“子集”，它生成给定集合的所有子集：

如何在另一个函数中组合 map、foldl 和 filter 以返回所有元素总和为 0 的子集？

**例子： **

给定一个 nXn 矩阵。并给出一些不同形状/大小的对象，如下所示。如何有效地绑定网格上的所有对象？

形状如下图所示：

“绑定”意味着在 nXn 网格上排列对象。一个对象的大小可以是 1,2，... 图像中显示了前 7 个大小的形状。