对于碎片整理算法，我需要解决以下问题：给定正整数的集合，提取尽可能多的子集，总和为给定值 . 集合中的每个项目只能出现在一个子集中 .
贪心算法（迭代正常子集和）不起作用，例如：
collection: 3 5 8 4 5 1 1 1 1 1, targeted sum: 10
1. subset: 5 1 1 1 1 1
there is no other subset
but:
1. subset: 8 1 1
2. subset: 5 4 1
3. subset: 3 5 1 1
如您所见，如果我选择以前的子集很差，那么解决方案并不是最佳的 . 我该如何解决这个问题？我已经实现了“正常”子集和 .
编辑：解决方案可能是先使用小子集吗？此外，这个问题与如何找到可能的子集数量的问题没有重复 . 我想找到尽可能多的 disjoint 子集 .
谢谢，菲尔
4 回答
对于问题的复杂性，它是强烈意义上的NPC . 这是3-Partition问题的后续问题：
我们需要来自三个分区问题的一个额外信息（这是其硬度证明的直接结果）：
对于你的问题的情况，我们可以假设输入由3m元素组成，给定值是B，对于每个元素a∈S我们有B / 4 <a <B / 2 . 然后我们可以找到m个集合，使得当且仅当我们能够解决三个分区时，每个集合都具有总和B. （注意，范围约束会自动强制每组中有3个元素） .
如果您允许回溯（即，能够返回并撤消先前的决定），那么您可以搜索整个可能性空间并确保找到您的解决方案 . 不是最有效的，但它的工作原理 .
或者你可以 Build 在@Druid的注释上：找到所有可能的子集，并搜索这些子集以找到你的分区，允许重复子集 . 您可以添加想要在较大子集之前尝试较小子集的启发式（为将来的选择留出更多灵活性） .
这个问题可能是NP-hard *，所以让我描绘一个O（2 ^ n * n）时间算法 .
让输入为多集U并让目标和为s . 想象一下在与U的子集相对应的2 ^ n个顶点上的图形 . 当且仅当（1）Y = X - 对于X中的某些x时，存在从子集X到子集Y的弧，以及（2） （sum（U - X）mod s）x≤s，即我们不溢出当前分区 . 从U开始遍历此图并报告具有最小总和的子集的路径 .
*我的减少显示硬度来自一个名为3-dimensional matching的问题 . 假设匹配实例具有n个顶点，则找到n个数，使得所有三元组具有不同的和 . 应用概率方法，如果我们从1..n ^ 6随机均匀地选择所有n，则成功的概率大于11/12（一减（n选3）选择2三倍时<1 / n ^ 6失败概率对于每个），验证需要时间O（n ^ 3 log n） . 从技术上讲，我们必须去随机化;见my question on math.SE .
为了准备这个问题的输入，对于与数字x相关联的每个顶点，输出n ^ 12 x . 对于可以匹配的每个三重x，y，z，输出n ^ 9 - x - y - z作为数字 . 目标是s = 3 n ^ 12 n ^ 9 . 一些繁琐的数学应该表明，目标总和的唯一子集对应于三维匹配的三元组 .
我创建了一个递归过程来查找所有子集和 . 它主动确定集合中的数字是太大还是太小而不是父节点 . 我在Nodejs中编写了一个运行良好的程序 . 只需重新访问它以进行优化和重构代码 .
对于所有正数的集合，可以对我的代码进行许多启发式和优化 .
你可以在这里阅读我手工做的数学：https://medium.com/@clint.mulligan/innovative-solution-to-the-subset-sum-problem-10a19f87056b
这里是代码的链接：https://github.com/ClintMulligan/subset-sum-finder .
Eseentially该集合已排序 . 第一个数字被认为是包含在一般树中的父节点 . 相关数据bieing数字所属的整数集，即正数或负数 .
作为父节点太大是| n | > |目标总和 - （对面组）|并且也是小是（同一组）<目标总和
如果其中任何一个为真，则考虑下一个数字 . 如果它们都为false，则将Number作为节点移动，并创建目标Sum的新子问题减去Number和剩余的set . 这样做直到每个子问题在解决方案或死胡同中结束 .
通过使用一些优化和进一步调查，我希望消除最死路一条 . 这不是那么糟糕的权利 .