问题标签 [subset-sum]

在今天的《卫报》（英国报纸）中，在 Chris Maslanka 第 43 页的“Pyrgic 谜题”部分，给出了以下谜题：

三位智者……去赫罗德做圣诞购物。Caspar 买了 Gold，Melchior 买了 Frankincense，Balthazar 买了一份Daily Myrrh。收银员输入了每件物品的欧元数，并打算将这三个数字相加，但是却将它们相乘。...令人惊奇的是，结果完全相同：65.52 欧元。三个总和是多少[我假设他的意思是三个数字]？

我的解释是：找到a、b和c使得a + b + c = abc = 65.52 （确切）其中a、b和c是不超过两位小数的正十进制数。因此a、b和c也必须小于 65.52（大约）。

因此，我的方法是：我将找到a、b和c的所有候选集，其中a + b + c = 6552 和a、b和c是 {1 ... 6550} 的整数（理论上我已经将所有操作数相乘为方便起见，减 100）。然后，对于所有候选集，通过将所有操作数除以 100 然后将它们相乘（使用任意精度算术）来满足另一个条件是微不足道的。

正如我所看到的，这是子集和问题的一个实例。所以我实现了一个脏（指数时间）算法，它找到了一个不同的解决方案：a=0.52，b=2，c=63。

好的，对于子集和问题有更好的算法，但你不认为这对于普通的卫报读者来说有点遥不可及吗？

第 40 页列出了答案：

这很容易，通过反复试验。猜猜每日没药的价格为 52 便士。但是乘以 0.52 大约是减半，所以我们需要一个和大约为 2；所以试试 2 X 63 X 0.52。等等瞧。这个答案是独一无二的吗？

好吧，我们知道答案是独一无二的（忽略 2、63 和 0.52 的其他排列）。

我想知道的是：这怎么可能“容易”？我将这个谜题描述为子集和问题的一个例子是否正确？我是否忽略了可用于简化解决方案的难题的某些特征？是否有人能够采用类似的“反复试验”方法，如果可以，他们可以带我完成吗？Chris Maslanka 是否对 NP 完全问题毫不畏惧？

我正在学习子集和问题，我想在这里问一些问题

(1)子集和算法

刚才看了这个链接的C代码，不知道为什么作者可以定义？

S[i,0]意味着subset[1,...i]总和0，为什么它可以分配给true.？如果想打印子集的内容，我该如何修改这个算法？因为好像禁止与作者私聊，所以不得不贴出来。

（2）如果数组中有负数，我试图测试它不适合。如何定义和的初始S[i,0]值S[0,j]？

谁能帮我澄清一下？

提前致谢！

SO上有很多子集问题和答案，但不知何故，我找不到针对我的具体问题的解决方案。

我需要找到轨道段的数量和长度来构建长度为 n 的轨道。段的长度：8、10、12、14、16、18、20、22、24 英尺 数量最多可达 4 段 轨道长度约为 20 到 100 英尺（并且总是偶数）

这是一条真正的赛道。段的顺序无关紧要。然而，有优选的尺寸组合。所有长度相等或彼此接近的都比大/小组合更可取。

IE：

• 70 => 20,20,20,10 很容易选择，但首选 16,18,18,18
• 60 => 20,20,20 优于 14,14,14,18

如果需要，我可以举出更多例子。

我不是在寻找一个最佳解决方案，而是寻找一小组可能的最佳解决方案。最终一个人会选择，这是关于建议最佳选择。

到目前为止，我所做的如下。它正在工作，只是看起来很复杂。

我从这篇文章Algorithm 中获取了基本算法，以查找大小为 n 的列表中的哪些数字总和到另一个数字。我在这段代码中所做的只是把它变成整数。它返回所有可能的组合。最多 5 个或更多曲目。

为了进一步减少结果集，我做了一些 Linq

此代码将产生以下结果，以 60 运行

或 80 这个

所以我的最终结果（4&5）实际上接近我所需要的。

但是我必须为任何可能的 3 轨道解决方案再次编写相同的代码，也许还有 2 轨道。

那么结果是否需要相互比较（不知何故，不确定如何）。这一切让我觉得我错过了什么。感觉很复杂，感觉不对。我错过了什么？

我开始使用错误的算法吗？一旦解决了我的问题，他们会更好吗？

假设您有一些数组，其中包含您知道都是正数且小于数字 N 的元素。

有人可以给我一个算法的一般高级描述，以找出数组中是否存在某个子集，其中所有元素加起来正好等于 N？

它不需要特别高效；我正在使用的设备非常小。

给定两个数字列表和一个总计列表（没有任何特定顺序）：

我怎样才能找到所有成对的集合，d使得d[k] = (a[i], b[j])从c[k] = a[i] + b[j]a 和 b 中使用对而不替换？（所有列表都可以有重复项）

对于c = [7,7,7]：

（1个答案，因为所有排列本质上都是等价的）

我想用长度约为 500 的列表来做这件事，所以天真的匹配/回溯搜索是不可能的。

我有一套硬币 1,2,4,10,20,40,100,200,400,1000,2000 美分。我想知道有多少种方式可以支付一定金额（<= 6000）。我目前在 c++ 中的解决方案是使用动态编程，如下所示：

但是我的输出不正确：-956301262。是因为任何溢出问题吗？

我刚开始Backtracking在大学学习算法。不知何故，我设法为子集和问题制作了一个程序。工作正常，但后来我发现我的程序并没有给出所有可能的组合。

例如：目标总和可能有一百个组合，但我的程序只给出 30 个。这是代码。如果有人能指出我的错误是什么，那将是一个很大的帮助。

当我运行程序时：

虽然 4、8 也是一种解决方案，但我的程序并没有显示出来。输入数量为 100 或更多时，情况更糟。至少会有 10000 个组合，但我的程序显示 100 个。

我试图遵循的逻辑：

1. 只要子集的总和保持小于或等于目标总和，就将主 SET 的元素纳入子集。
2. 如果将特定数字添加到子集总和使其大于目标，则不接受它。
3. 一旦它到达集合的末尾，并且没有找到答案，它就会从集合中删除最近使用的数字，并开始查看最近删除的数字位置之后的位置中的数字。（因为我存储在数组's'中的是主SET中所选数字的位置）。

所以这是我到目前为止的代码。如果总和存在，它会起作用并返回true，但我似乎无法找到一种方法来打印出它用来查找总和的整数。有没有办法我可以重新编写它以使其与 true 一起做到这一点，或者我应该如何编写代码以便它可以做到这一点？

I am new to C++ and am writing a sum of subsets program that takes in a user defined set of numbers, the first number of which is considered to be the total. I have tried using DDD to debug this program, however I continue to get an out-of-bounds error. I cannot seem to find out why this is happening. Any clues? Thanks. Here is the error:

Code:

.

.

.

我已经阅读了其他一些讨论，但不知道如何修复我的程序。随着它的递归，我的索引计数器最终变得太大，并且由于它超出了范围（或者至少我认为这是正确的），因此承诺不起作用。我该如何解决这个问题，以使索引永远不会变得太大？