问题标签 [knapsack-problem]

实际上，我有一组具有概率的对象，我想查看它们中的每个可能组，按照假设它们是独立的，它们都是真实的可能性有多大 - 即按降序排列子集元素的乘积 - 如果概率相同，则按长度顺序排列（因此 (1, 0.5) 在 (0.5) 之后）。

示例：如果我有[ 1, 0.5, 0.1 ]我想要[ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

从本质上讲，这意味着我想按顺序迭代一组元素的幂集，并且我可以相当容易地生成它，对其进行排序并完成。然而，powersets 变得相当大很快，我希望我通常会想要第一个子集，我宁愿不生成数千个子集的列表，对它们进行排序，然后再看第三个。这就是 python 生成器希望拯救这一天的地方！

更正式的问题说明，我需要找到一种方法sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True)，作为生成器，或者以其他方式让我避免构建和排序整个列表。

我有理由确定这与背包问题以及子产品问题有关，但我真的很难找到一个很好的算法来解决它，非常感谢您的帮助:-)。在最坏的情况下（一直迭代到最后），它比构建+排序整个事情要慢并不是问题，它只需要更好的最佳情况（比如说，在前 10% 内）性能。

我已经在 Haskell 中编写了0-1 背包问题。我对迄今为止所取得的懒惰和普遍性水平感到相当自豪。

我首先提供用于创建和处理惰性二维矩阵的函数。

然后我为给定的背包问题制作一个特定的表

最后用几个辅助函数来查看表格

这很容易。但我想更进一步。

我想要一个更好的表数据结构。理想情况下，它应该是

• 未装箱（不可变） [编辑] 没关系
• 懒惰的
• 无界
• O(1)建设时间
• O(1)查找给定条目的时间复杂度，
  （更实际地，在最坏的情况O(log n)下，其中 ni*j用于查找第 i 行第 j 列的条目）

如果您能解释您的解决方案为什么/如何满足这些理想，则可以加分。

如果您可以进一步概括knapsackTable，也可以加分，并证明它是有效的。

在改进数据结构时，您应该尝试满足以下目标：

• 如果我要求最大权重为 10 的解决方案（在我当前的代码中，即indexTable knapsackTable 5 105 意味着包括项目 1-5），则只应执行最少的工作量。理想情况下，这意味着无需O(i*j)将表格的每一行的脊椎强制为必要的列长度。如果您认为 DP 意味着评估整个表格，您可以说这不是“真正的”DP。
• 如果我要求打印整个表格（类似于printTable knapsackTable 5 10），则每个条目的值应计算一次且仅计算一次。给定单元格的值应取决于其他单元格的值（DP 风格：想法是，永远不要重新计算相同的子问题两次）

想法：

• Data.Array有界:(
• UArray严格:(
• 记忆技术（关于Haskell中DP的问题）这可能有效

对我陈述的理想做出一些妥协的答案将被赞成（无论如何，由我），只要它们提供信息。妥协最少的答案可能是“接受”的答案。

所以对于一个练习题，我们应该设计一个动态规划算法，它是 0/1 背包问题的变体......基本上每个项目来自 4 个不同的来源，并且该项目只能从一个来源中获取。 .

即，

对于n = 10，如果您选择i = 16放置，则意味着您不会选择6, 26 or 36...

你能帮我解决这个问题并设计递推方程吗？

我有一个背包问题，指定的背包重量和重量计数。

我需要一种算法，当背包容量为 C、所需的重量计数为 N 并且有一个重量列表时，将重量打包到背包中。权重排序无关紧要。如果算法是递归的，那将是最好的。

例如：
我有一个背包女巫只能装 3 个重量，而他们的重量必须是 10，而我有这些重量：9、8、7、2、1。正确（也是唯一）答案是 7、2、1。

如果有人编写伪代码最好，但如果它是任何常见的编程语言都可以。

PS 任何提示也值得赞赏:)

[编辑]我需要一个算法，它给出的答案正好是 N 权重计数，它的权重正好是 C。

有谁知道如何从这个伪代码中实现 Java 中的子集和问题？

这真的让我很困惑，所以如果你能添加评论那就太好了！！！

所以我必须解决课堂上的背包问题。到目前为止，我已经想出了以下内容。我的比较器是确定两个主题中哪一个是更好选择的函数（通过查看相应的 (value,work) 元组）。

我决定迭代工作少于 maxWork 的可能主题，为了找到在任何给定轮次中哪个主题是最佳选择，我将我最近的主题与我们尚未使用的所有其他主题进行了比较。

问题是我不知道为什么这是错误的。我遇到了错误，我不知道我的代码哪里出错了（即使在输入打印语句之后）。帮助将不胜感激，谢谢！

有人可以用选择的编程语言（最好是Python，但我猜任何事情都可以）想出一个解决这个问题的方法：

我有各种轨道长度组，比方说：

和源轨道本身：

我需要务实地找到哪些曲目属于上述长度组。例如，前两个轨道属于第一组，因为它们的总长度等于组长度

提前致谢

编辑：这不是我的作业，因为那个时间已经过去了（我已经 30 多岁了），但这是我遇到的问题，而且我不是程序员。我会看看itertools，谢谢

编辑2：感谢您的建议。我制作了 Python 脚本，如果对我来说运行良好且快速。它肯定没有优化，但这里是骨架：

我很高兴我解决了这个问题，因为手动跟踪这将花费我更多的时间，哈哈

我没有问过使用遗传算法的背包问题。初始化我使用这种染色体[1] = [权重] [利润]，因为他的公式KP对染色体的评估权重x利润。不使用轮盘选择进入后。到 p (a) = 0.04761/0.19761 = 0.24092；p (b) = 0.1/0.19761 = 0.50604；p (c) = 0.025/0.19761 = 0.12651。那么setelag那个生成随机数，随机数可以之后，怎么会交叉呢？

请解释，请帮助我

我的问题如下-

我有一些数字，如下所示-

因此，如果我将以下数字作为输入，则输出应如下所示-

[输出是给定数字的总和，刚好大于输入]

我不只是想尝试每一种组合（即蛮力）来获得结果。所以只想问对于上述情况是否有任何有效的算法。

谢谢。

问题

我有一个看起来像这样的数据哈希。

GROUP_A 有 22 个帐户，他们正在使用 440GB 的数据......等等。有几百个这样的组。有些人有很多帐户但使用的存储空间很少，有些人只有少数用户并使用大量存储空间，有些只是平均水平。

我有 X 个存储桶（服务器），我想将这些帐户组放入其中，并且我希望每个存储桶的帐户数量大致相同，并且每个存储桶也包含大致相同数量的数据。组的数量并不重要，所以如果一个存储桶有 1 组使用 500GB 数据的 1000 个帐户，而下一个存储桶有 10 组使用 450GB 数据的 97 个帐户（总共 970 个）......我会称之为好。

到目前为止，我还没有想出一个算法来做到这一点。在我的脑海中，我可能正在考虑这样的事情？

我仍然认为有更好的方法来解决这个问题，但它并没有出现在我身上。如果有人有任何想法，我愿意接受建议。

马特

解决方案 1.1 - 蛮力更新

嗯....这是第一次尝试的更新。这仍然不是一个“背包问题”的解决方案。只需暴力破解数据，以便帐户在存储桶之间保持平衡。这次我添加了一些逻辑，以便如果一个存储桶的帐户完整百分比与数据相比更高......它将根据帐户数量找到最适合的最大组（按数据）。与我的第一次尝试相比，我现在的数据分布要好得多（如果您想查看第一次尝试，请参阅编辑历史记录）。

现在我按顺序加载每个存储桶，填充存储桶一，然后存储存储桶二，等等......我想如果我要修改代码以便同时（或几乎同时）填充它们，我会获得更好的数据平衡。

例如，第 1 部门进入存储桶 1，第 2 部门进入存储桶 2，等等……直到所有存储桶都有一个部门……然后再次从存储桶 1 开始。

……结果……

(379 * 6 <> 2279) 我仍然需要弄清楚当 MAX_ACCTS 不能被桶数整除时如何计算。我尝试在 AVG_ACCTS 值上添加 1% 填充，在这种情况下，我认为平均值为 383，但随后所有存储桶都说他们有 383 个帐户……这不可能是真的，因为那时有存储桶中的帐户数量超过 MAX_ACCTS 个。我在我还没有找到的地方的代码中有一个错误。