问题标签 [subset-sum]

假设我想找到所有 5 个单数、非重复数字，加起来为 30...我最终会得到 [9,8,7,5,1], [9,8,7 ,4,2], [9,8,6,4,3], [9,8,6,5,2], [9,7,6,5,3] 和 [8,7,6, 5,4]。这些集合中的每一个都包含 5 个不重复的数字，它们加起来为 30，即给定的总和。

任何帮助将不胜感激。即使只是我使用的一个起点也很棒。

我想出了一种方法，这似乎还有很长的路要走：获取所有唯一的 5 位数字（12345、12346、12347 等），将数字相加，看看它是否等于给定的总和（例如 30)。如果是，请将其添加到可能的匹配集列表中。

我这样做是为了一个个人项目，这将帮助我解决 Kakuro 难题，而无需一次真正解决整个问题。是的，它可能是作弊，但它......它不是那么糟糕......：P

是的，这是一项家庭作业/实验室作业。我很有趣想出/找到一种算法（我可以理解：P）来使用“回溯”来解决子集和问题。

有人有一些有用的资源吗？我花了最后一个小时左右的时间在谷歌上搜索，并不太想找到我认为我可以实际使用的东西。xD

谢谢！

我想出了一个新的算法来解决子集和问题，我认为它是在多项式时间内。告诉我我要么错了要么完全是个天才。

快速入门事实：

子集和问题是一个 NP 完全问题。在多项式时间内求解它意味着 P = NP。
一组长度为 N 的子集的数量为 2^N。

另一方面，长度为 N 的唯一子集的数量最大为整个集合的总和减去最小元素，或者，任何子集可能产生的和的范围在所有负元素的总和之间和所有正元素的总和，因为没有总和可能大于或小于所有正或负总和，当我们添加额外元素时，它们以线性速率增长。

这意味着随着 N 的增加，重复子集的数量呈指数增长，而唯一有用的子集的数量仅线性增加。如果可以设计一种算法来尽早删除重复的子集，我们将在多项式时间内运行。一个简单的例子很容易取自二进制文件。仅从作为 2 的幂的数字，我们可以为任何整数值创建唯一的子集。因此，任何涉及任何其他数字的子集（如果我们有 2 的所有幂）都是重复的和浪费的。通过不计算它们及其导数，我们几乎可以节省算法的所有运行时间，因为与任何整数相比，作为 2 的幂的数字都是对数出现的。

因此，我提出了一个简单的算法，该算法将删除这些重复项并省去计算它们及其所有导数的麻烦。

首先，我们将对只有 O(N log N) 的集合进行排序，并将其分成两半，正数和负数。负数的过程是相同的，所以我将只概述正数（集合现在仅表示正数，只是为了澄清）。

想象一个由 sum 索引的数组，其中包含所有可能的正边结果总和的条目（记住，这只是线性的）。当我们添加一个条目时，值是子集中的条目。就像，数组 [3] = { 1, 2 }。

一般来说，我们现在开始枚举集合中的所有子集。我们通过从一个长度的子集开始，然后添加到它们来做到这一点。当我们拥有所有独特的子集时，它们形成一个数组，我们只需按照 Horowitz/Sahni 中使用的方式迭代它们。

现在我们从“第一代”价值观开始。也就是说，如果原始数据集中没有重复的数字，则保证这些值中没有重复。也就是说，所有单值子集，以及集合的所有长度减去一个长度的子集。这些可以通过对集合求和并依次减去每个元素来轻松生成。此外，集合本身是有效的第一代总和和子集，以及子集的每个单独元素。

现在我们做第二代价值观。我们遍历数组中的每个值和每个唯一子集，如果没有，我们添加它并计算新的唯一子集。如果我们有重复，就会发生乐趣。我们将其添加到碰撞列表中。当我们添加新的子集时，我们检查它们是否在冲突列表中。我们以不太理想的（通常更大，但可以是任意的）相等子集为关键。当我们添加到子集时，如果我们会产生碰撞，我们什么也不做。当我们来添加更理想的子集时，它会错过检查并添加，生成公共子集。然后我们只是重复其他几代人。

通过以这种方式删除重复的子集，我们不必继续将重复项与集合的其余部分组合，也不必继续检查它们是否有冲突，也不必对它们求和。最重要的是，通过不创建非唯一的新子集，我们不会从它们生成新子集，我相信这可以将算法从 NP 转变为 P，因为子集的增长不再是指数级的——我们丢弃它们中的绝大多数在它们可以在下一代中“复制”并通过与其他非重复子集组合来创建更多子集之前。

我认为我没有很好地解释这一点。我有照片……它们在我的脑海里。重要的是，通过丢弃重复的子集，您几乎可以消除所有的复杂性。

例如，想象一下（因为我是手工做这个例子）一个简单的数据集，它从 -7 到 7（不是零），我们的目标是零。排序和拆分，所以我们剩下 (1, 2, 3, 4, 5, 6, 7)。总和是 28。但 2^7 是 128。所以 128 个子集适合 1 .. 28 的范围，这意味着我们事先知道 100 个集合是重复的。如果我们有 8 个，那么我们将只有 36 个插槽，但现在有 256 个子集。所以你可以很容易地看到，现在被骗的数量是 220，是以前的两倍多。

在这种情况下，第一代的值为 1, 2, 3, 4, 5, 6, 7, 28, 27, 26, 25, 24, 23, 22, 21，我们将它们映射到它们的组成部分，所以

现在要生成新的子集，我们依次获取每个子集并将其添加到彼此的子集中，除非它们具有相互子集，例如 28 和 27 具有hueg 相互子集。因此，当我们取 1 并将其添加到 2 时，我们得到 3 = { 1, 2 } 但请等待！它已经在数组中。这意味着我们现在不会将 1 添加到任何已经包含 2 的子集中，反之亦然，因为这是 3 的子集的重复。

现在我们有

现在我们将 2 添加到所有。

3?

如您所见，即使我每次都在添加新的子集，但数量只是线性增加。

4？

5?

现在我们有了范围内的每个值，所以我们停下来，将 1-28 添加到我们的列表中。对负数重复，遍历列表。

编辑：

在任何情况下，这个算法都是完全错误的。具有重复总和的子集不是出于可以从中派生子集的目的的重复，因为它们的到达方式不同——即它们不能被折叠。

有谁知道相等 k 子集算法的良好有效算法？最好是可以处理 100 个元素向量的 c 或 c++ 可能具有复杂性和时间估计

前任。9 元素向量

x = {2,4,5,6,8,9,11,13,14}

我需要生成总和 = 24 的所有 k=3 不相交子集，该算法应检查是否有 k 个不相交子集，每个子​​集的总和为 24，并按升序（在子集中和子集之间）列出它们或查看解决方案不存在

解决方案

解决方案 1：{2 8 14} {4 9 11} {5 6 13}

解决方案 2：{2 9 13} {4 6 14} {5 8 11}

谢谢

首先，我要说我对理论之类的东西知之甚少。但我想知道这是一个 NP 还是 NP 完全问题。这听起来像是子集和问题的一个特例。

无论如何，我最近一直在玩这款名为 Alchemy 的游戏，它引发了这个想法。基本上，您从 4 个基本元素开始，然后将它们组合成其他元素。

因此，例如，如果您愿意制作元素，这是一个简短的“食谱”

因此，假设一台计算机只能创建 4 个基本元素，但它可以创建多组元素。因此，您编写一个程序来通过组合其他元素来制作任何元素。该程序将如何处理创建灯泡的列表？

很明显，火+空气=能量，土+土=沙，沙+火=玻璃，能量+玻璃=灯泡。

但是我想不出任何方法来编写程序来处理列表并在不使用蛮力类型方法并检查每个元素并检查其配方的情况下弄清楚这一点。

这是一个NP问题吗？或者我只是无法弄清楚这一点？

我正在解决这个问题：

子集和问题将一组X = {x1, x2 ,…, xn}整数n和另一个整数作为输入K。问题是检查是否存在其元素总和的子X'集并找到子集（如果有）。例如，如果和那么答案是因为子集的总和为。为运行时间至少为 的子集和实现算法。XKX = {5, 3, 11, 8, 2}K = 16YESX' = {5, 11}16O(nK)

注意复杂性O(nK)。我认为动态编程可能会有所帮助。

我找到了一个指数时间算法，但它没有帮助。

有人可以帮我解决这个问题吗？

假设我有一个数组 int [] arr={1,2,4,5,7} 并且还有数字 6 所以我需要结果为 01100 这意味着数组中的 2+4=6 所以结果将如果总和中的数字为 0，则为 1，否则我还需要结果中的位数与数组长度相同

我需要执行此操作的 java 方法

您将如何测试给定数字集的所有可能的加法组合，N以便它们加起来为给定的最终数字？

一个简单的例子：

• 要添加的一组数字：N = {1,5,22,15,0,...}
• 期望的结果：12345

我的任务是编写一个算法来计算整数矩阵的最大二维子集。- 但是我对这种算法的帮助不感兴趣，我更感兴趣的是了解可能解决这个问题的最坏情况的复杂性。

我们当前的算法就像 O(n^3)。

我一直在考虑类似分而治之的事情，通过将矩阵拆分为多个子矩阵，只需将矩阵中的元素相加即可；从而限制了为了找到近似解而必须考虑的矩阵的数量。

我创建了两个函数来帮助我解决子集总和问题。不过，我似乎遇到了错误。它告诉我，我将两个参数传递给list-sum. 我已经在这个程序上玩了几个小时了。我想知道是否有人能发现问题。

这是我的list-sum：

这是我使用的函数list-sum：

它告诉我，我用一个参数调用了“compound-procedure #(number) ssum”，并且它需要两个参数。我把它作为(ssum 8 (list 1 3 5 7)).

我的问题是：

1. 我是否正确设置了我的功能？
2. 有没有一种更简单的方法可以将我的列表中的数字相加ssum？
3. 我对Scheme也很陌生。如果您看到缩短代码的明显方法，请随时纠正我。