问题标签 [subset-sum]

我有几个数字数组（数组的每个元素只能取0或1的值）像这样

我希望找到这样的子集，以便在对数组求和时，生成的数组具有单个元素，这些元素是 2 的倍数。例如，v1+v2+v3 给出的结果数组为 2、2、0、2、2。结果数组可以具有任何 2 的倍数的值。

另一个例子：

在此示例中，v1+v2+v5 和 v3+v6+v7 是合适的答案。

我有一个蛮力解决方案，但我想检查是否有更有效的方法。这相当于子集和问题吗？

我一直在为这个我被要求回答的问题（从技术上讲是家庭作业）而汗流浃背。我考虑过一个哈希表，但我有点坚持我如何使这项工作的确切细节

这是问题：

给定k组整数A ₁ , A ₂ ,.., A _k的总大小为 O( n )，您应该确定是否存在 a ₁ ϵ A ₁ , a ₂ ϵ A ₂ ,.., a _k ϵ A _k ,使得a ₁ + a ₂ +..+ a _{k -1} = a _k。您的算法应该在 T _k ( n ) 时间内运行，其中 T _k( n ) = O( n ^{k /2} × log n ) 对于偶数k， O( n ^{( k +1)/2} ) 对于k的奇数值。

谁能给我一个大致的方向，以便我可以更接近解决这个问题？

字谜：

字谜是一种文字游戏，是重新排列单词或短语的字母以产生新单词或短语的结果，使用所有原始字母一次；

子集和问题：

问题是这样的：给定一组整数，是否存在总和为零的非空子集？

例如，给定集合 { -7, -3, -2, 5, 8}，答案是肯定的，因为子集 { -3, -2, 5} 的总和为零。问题是NP完全的。

现在假设我们有一个包含 n 个单词的字典。现在，字谜生成问题可以描述为在字典中找到一组单词（n 个单词），这些单词用完输入的所有字母。所以它不会变成一种子集和问题。

我错了吗？

我很乐意得到一些帮助。

我有以下问题：

我得到了一个数字列表seq和一个目标数字，我需要写两件事：

1. True如果子序列的总和等于目标数，则返回递归解决方案，False否则返回。例子：

   /li>

2. 其次，我需要使用我在上一个解决方案中编写的内容编写一个解决方案，但现在使用一个字典，其中键是元组： (len(seq),target)

对于 1 号，这是我到目前为止所做的：

不确定我做对了，所以如果我能得到一些意见，我将不胜感激。

对于 2 号：

我无法获得记忆来给我正确的答案，所以我很高兴在这里得到一些指导。

感谢任何愿意提供帮助的人！

好吧，如果有人知道的话，我正在开发的纸牌游戏与 Scopa 非常相似。一副牌包含 40 张牌，分为 4 种不同的花色，每张 10 张牌（ace => 价值 1，二 => 价值 2，三 = ...，四，五，六，七，无赖，女王，国王 => 价值 10 ）。有 2 个玩家（实际上是一个 AI 和一个人类玩家），他们手里有 4 张牌。

桌上有 4 张免费牌可以拿走，玩家只能在遵守以下规则的情况下拿走它们： 1) 宫廷牌（无赖、皇后和国王）只能拿相同的宫廷牌（例如，如果我有一张皇后，我只能从桌子上拿一个皇后）。2) 数字卡（从 ace 到 7）可以取相同的数字卡或更小的数字卡（例如，如果我有一个 7，我可以取一个 7 或 { a ace, a 6 } 或 {a 3, a 4 } 或 { 一个 ace，三个 2 })。

现在是时候找出 AI 在轮到它时最终可以拿走哪些牌了：

你认为这个算法可以以某种方式改进吗？我正在尝试尽可能地缩短此代码，以便它易于调试和易于维护......此外，如果有人有更优雅的解决方案来避免重复组合，我真的非常感谢它（我不想同时获得 {红桃 A，黑桃两张 } 和 {黑桃两张，红桃 A } ......只有其中一个）。

非常非常感谢提前！

我知道这是一个 NP 难题，但我们的很多用户一直在请求此功能（基本上，您当前订单中的任何一组商品是否符合我们正在运行的交易之一？或者任何一组您当前订单中的商品加上其他商品是否符合条件？）

由于提供功能更多的是为了用户方便而不是找到正确的答案，我一直在考虑使用快捷方式来做到这一点而不会花费太长时间，例如如果有超过 X 个项目，则不运行算法，其中 X 是导致明显的数字滞后，或仅通过算法运行最近添加的 X 项。

在此之前有没有人处理过类似的问题可以提供建议？

我正在编写这个函数，我想用整数打印给定列表的所有子列表。这些整数的总和应该等于给定的数字n。还有一个i从值 0 开始的帮助变量。列表和每个子列表都是ArrayList. 所以这个方法现在看起来像这样：

当然我已经有了方法sum()。该方法现在执行此操作：假设numbers = [1, 3 , 4]and n == 4，那么该方法应该打印[4]and [1 ,3]，但它只打印[1, 3]? 我认为 for 循环必须做到这一点，对吗？如果有人让我走上正轨，我将不胜感激。

更新：我赋予该方法的值：

更新 2：

我忘了说我希望它是递归的:)

考虑这种解决子集和问题的方法：

我从这里得到它：

http://news.ycombinator.com/item?id=2267392

还有一条评论说可以使其“更高效”。

如何？

此外，还有其他方法可以解决问题，至少与上述方法一样快吗？

编辑

我对任何会导致加速的想法感兴趣。我发现：

https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2

其中提到了线性时间算法。但是我没有那张纸，也许你们，亲爱的人们，知道它是如何工作的吗？也许是一个实现？也许完全不同的方法？

编辑 2

现在有后续：
Pisinger 的 Subset sum algorithm 的快速解决方案

从这些问题子集和问题 和具有固定子集大小的和子集之后，我想知道解决子集和问题的一般算法是什么，我们被迫使用完全 k 个整数，k <= n。

Evgeny Kluev 提到他会选择对 k = 4 使用最优方法，然后对 k-4 使用蛮力方法，对其余部分使用最优方法。任何人都可以在这里通过蛮力方法结合最佳 k=4 算法来阐明他的意思吗？

也许有人知道更好的通用解决方案？

这是我之前的问题的后续。我仍然觉得这是一个非常有趣的问题，因为有一种算法值得更多关注，所以我将其发布在这里。

来自Wikipedia：对于每个 xi 为正且以相同常数为界的情况，Pisinger 找到了一种线性时间算法。

有一篇不同的论文似乎描述了相同的算法，但对我来说有点难以阅读，所以请 - 有人知道如何将第 4 页（balsub）中的伪代码翻译成工作实现吗？

以下是我迄今为止收集的一些建议：

http://www.diku.dk/~pisinger/95-6.ps（论文）
https://stackoverflow.com/a/9952759/1037407
http://www.diku.dk/hjemmesider/ansatte/pisinger /codes.html

PS：我并不真的坚持这个算法，所以如果你知道任何其他类似性能的算法，请随时在下面提出建议。

编辑

这是 oldboy 在下面发布的代码的 Python 版本：