问题标签 [subset-sum]

寻找针对这种特定情况的子集和问题的解决方案（在 C# 或其他算法中）：

1) 集合中大约有 1,000 个数字（可能会增长到几千个）

2) 总额达到数十亿

3) 数字是货币值，所以有两位小数的精度（例如 2,345.17）

4）集合中的数字可以是正数和负数（所以处理净和）

然后我需要重复此搜索（使用相同的数字集）但总和不同，最多 1,000 次。最后整个过程运行 1000 次。因此，我们正在查看 1,000,000 次运行。目标是在 2 分钟内完成。这意味着每次运行不应超过 0.12 毫秒。

这可行吗？

-克里普

有人可以指导我如何解决这个问题。

给定一个集合 S，其中有 k 个元素。

现在我们必须将集合 S 划分为 x 个子集，使得每个子集中的元素数量之差不超过 1，并且每个子集的总和应尽可能接近。

示例 1：{10, 20, 90, 200, 100} 必须分为 2 个子集

解决方案：{10,200}{20,90,100}

总和是 210 和 210

示例 2：{1, 1, 2, 1, 1, 1, 1, 1, 1, 6}

解决方案：{1,1,1,1,6}{1,2,1,1,1}

总和是 10 和 6。

可能重复：
相等 k 个子集算法

假设我有一组数字，我想将这些数字分成 k 个子集，以便这些数字均匀分布。通过均匀分布，我的意思是子集中的值的总和最接近其他子集的其他总和。我们可以对这个问题实施 DP 解决方案吗？

请建议！

以下问题：

我有一个 MySQL 数据库，里面有歌曲。该数据库具有以下结构：

用户应该能够在 php 表单中输入特定时间，并且 php 函数应该为他提供所有可能的歌曲组合列表，这些组合加起来等于给定时间 ±X 分钟。

因此，如果用户想听 1 小时 ±5 分钟的音乐，他会在表格中输入 60 分钟和 5 分钟的阈值，并会收到所有可能的歌曲集，总时长为 55 到 65 分钟。它不应该打印出重复项。

我已经找到了解决这个问题的几种方法，但它们只给了我加起来为 X 的持续时间，而不是歌曲名称等。所以我的问题是如何解决这个问题，以便它给我返回添加的歌曲的 ID到所需的时间或打印出带有相应歌曲名称的列表。

这似乎是我找到的最佳答案之一，但我无法将其适应我的数据库。

我有这个代码......这正是我需要的。它在一个预定义的整数数组中搜索总和为目标整数的两个整数。但是，当将值放入向量中时，它不是将它们放在单元格中，而是将所有值放在一起。即对于 int array[50,40,30,20,10] 和目标 50，而不是返回 [[50][40,10][30,20]...等]，它打印 [[50,40 ,10,30,20...]] 我该如何解决这个问题？

尝试为 subsetSum 编写算法...它应该找到给定向量的所有可能子集，然后找到哪些子集加起来达到目标​​值。但是，我不断收到 nullpointerexceptions 和其他一些错误。有人可以帮我吗？我处于一个紧张的位置，大脑几乎无法运作。非常感激。谢谢。

第 78 行是 subsetSum 方法中第一个 for 循环的行。

我什至不确定这是否可以在多项式时间内完成。

问题：

给定两个实数数组，

和一个数字k，找到 的子集A'，A (A' = (a[i(1)], a[i(2)], ..., a[i(k)]))其中恰好包含k元素，使得(sum a[i(j)])/(sum b[i(j)])最大化，其中
j = 1, 2, ..., k。

例如，如果k == 3,{a[1], a[5], a[7]}是结果，那么

应该大于任何其他组合。有什么线索吗？

我真的很感激对这个实际问题的一些评论。

快速描述。 我有可变数量的链接，可用于构成给定的皮带宽度。问题是，每个链接有多少。选择标准：最好使用较长的项目。

例子。 假设我们要创建一个皮带宽度，W = 1024.0 其中一个模型具有以下链接长度：L = [34.0, 65.0, 96.0, 126.0]

问题是，每个链接有多少来制作宽度。

这是我尝试过的一些方法。

1.贪婪（选择最长的第一个以满足标准） c = [0,0,0,8] 其中c是每个项目的计数。这留下了 16.0 的差距，我什至无法容纳 1 个最小的项目。贪婪很容易，但并不好。

2. 选择循环 不太容易，我认为这是一个难题。我尝试了很多策略：填充小物品，然后依次移除它们以适应下一个尺寸。

3. 背包法 不太合适，因为这是基于给定数量的物品。

4. 子集和问题 这是背包的一个子类，但我无法让它工作。

5. 装箱问题 听起来很相似，但我无法将其应用于我的问题。

6.蛮力（随机选择） 奇怪的是，这个找到了很多完全匹配。我使用计数的简单多项式作为评级。rating = n[0] + n[1]* 2 + n[2] *3 + n[4]**4 + ... 蛮力的解决方案之一是 [4, 0, 4, 4] 给出正好是 1024。问题是，这种方法通常会产生不同的选择，因此并不理想。

7.穷举搜索 不实用，因为选择太多。

8. 模拟退火 从蛮力的成功来看，这看起来是一个不错的选择。有人可以给我举一个简单的例子吗（请不要是另一个旅行推销员）。

9. 遗传和粒子群 不确定这些。

现在，我陷入困境和沮丧。是否有可用于此问题的直接算法？

这是子集和问题的解决方案。它使用回溯。我已经考虑了两个多小时了，我就是无法理解。

编辑：根据我的理解，我在代码中添加了一些注释。如果我错了，请纠正我。

注意：这是一个有效的解决方案。它在使用 g++ 编译时工作。如果这看起来太令人讨厌，我很抱歉，但我只是从代码中不太了解，因此我无法给出太多解释。

我正在从 tardos 的算法设计书中阅读 NP 完整性，在证明子集总和是 NP 完全的部分，写到 -
为子集总和开发的算法的运行时间为 O(nW)。如果给出 100 个数字的实例，每个数字都是 100 位长，那么输入只有 100 * 100 = 10000 位，但 W 大约是 2^100。
我不明白这个说法，为什么是 W 2^100 ？base 对这个问题有什么影响，我的意思是，如果我们将其更改为其他 base x，W 会是 x^100 吗？如果我们将其更改为一元基数怎么办？
谢谢。