问题标签 [knapsack-problem]

这里我有使用背包算法计算最优值的代码（装箱NP-hard问题）：

我还需要显示包中包含的元素。我想创建一个数组来放置所选元素。所以问题是，我可以在哪一步执行这个选择？有没有其他更有效的方法来确定哪些项目已被拿走？

我希望能够知道给我最佳解决方案的项目，而不仅仅是最佳解决方案的价值。

剧透：我正在研究http://www.spoj.pl/problems/KNAPSACK/所以如果你不想为你破坏可能的解决方案，请不要偷看。

样板：

一些设置舞台的类型和助手：

主要功能：

这段代码有效；我尝试插入 SPOJ 示例测试用例，它会产生正确的结果。但是当我将这个解决方案提交给 SPOJ（而不是导入 Luke Palmer 的 MemoCombinators，我只是将必要的部分复制并粘贴到提交的源中）时，它超过了时间限制。=/

我不明白为什么；我之前问过一种执行 0-1 背包的有效方法，我相当确信这几乎是最快的：一个记忆函数，它只会递归地计算它绝对需要的子条目以产生正确的结果。我是否以某种方式搞砸了记忆？这段代码中是否有我遗漏的慢点？SPOJ 只是对 Haskell 有偏见吗？

我什至把{-# OPTIONS_GHC -O2 #-}提交的顶部，但唉，它没有帮助。我尝试了一个类似的解决方案，它使用Sequences 的 2D 数组，但它也因为太慢而被拒绝。

我正在自学基本的编程原理，但我陷入了一个动态编程问题。让我们以臭名昭著的背包问题为例：

给定一组项目，每个项目都有一个权重和一个值，确定要包含在集合中的每个项目的计数，以便总权重小于或等于给定限制并且总值尽可能大。

让我们将重量限制设置为 10，并给出两个列表：weights = [2,4,7] 和 values = [8,4,9]（我只是编造了这些）。我可以编写代码以在给定约束的情况下给出最大值——这不是问题。但是，如果我想知道我最终使用了哪些值呢？不是总价值——个别价值。所以对于这个例子，最大值将是权重为 2 和 7 的对象，总值为 8 + 9 = 17。我不希望我的答案读为“17”——我想要一个列表的输出比如：(8, 9)。这个问题可能很容易，但我正在处理的问题使用更大且具有重复数字的列表（例如，多个对象的值为 8）。

让我知道是否有人能想到任何事情。一如既往，对社区充满爱和感激。

因此，标准的多项选择背包问题允许从每个类别中选择一项来创建最佳背包。但是，我将如何修改此算法以允许选择 0 或 1 个项目？即不需要从每个类中选择一个项目以获得最佳解决方案，但最多可以从一个类中选择一个项目。它只是不允许从一个类中选择任何项目的相同算法吗？

谢谢

我刚在想，

我想对背包问题做一个变体。

想象一下最初的问题，具有不同权重/值的项目。

我的版本除了具有正常的权重/值外，还包含一个“组”值。

例如。项目 1[5 公斤，600 美元，电子产品] 项目 2 [1 公斤，50 美元，食品]

现在，有一组这样的项目，我将如何编写背包问题以确保从每个“组”中选择最多 1 个项目。

笔记：

1. 您无需从该组中选择项目
2. 每组有多个项目
3. 您仍在减轻重量，最大化价值
4. 组的数量及其值是预定义的。

我只是在这个阶段编写代码草稿，并且我选择使用动态方法。我了解常规背包问题的动态解决方案背后的想法，如何更改此解决方案以合并这些“组”？

这就是我到目前为止所拥有的，需要添加它，以便它每次解决这个问题时都会从它所在的组中删除所有相应的项目。

这是我的任务

背包问题是计算机科学中的经典。在其最简单的形式中，它涉及尝试将不同重量的物品装入背包，以便背包最终具有指定的总重量。你不需要适应所有的项目。例如，假设您希望您的背包正好重 20 磅，并且您有五件物品，重量分别为 11、8、7、6 和 5 磅。对于少量物品，人类非常擅长通过检查来解决这个问题。所以你大概可以算出，只有 8、7 和 5 的项目组合加起来是 20。

我真的不知道从哪里开始写这个算法。当应用于阶乘和三角形数时，我理解递归。然而我现在迷路了。

Can a typical Lisp dialect solve problems using the bottom-up "dynamic programming" approach?

(Please note: I'm not talking about "memoization" which, as far as I understand, is trivial using any Lisp dialect. I'm really talking about bottom-up Dynamic Programming, where you build, for an example, your array bottom up and then use the elements you just introduced to compute the next ones.)

For example, using dynamic programming, the "0-1 knapsack" problem can be solved in pseudo-polynomial time for inputs on which any other method would fail.

An imperative (incomplete) solution is:

Is such a thing possible to do in the various Lisp dialects? If no, why not?

给定通常n的项目集（例如，每个项目都是无限的），具有权重和值：

和一个目标重量W，我需要选择总重量至少 W和总值最小的项目。

在我看来，这就像整数/无界背包问题的变体（或在某种意义上相反）。任何帮助制定 DP 算法将不胜感激！

我在给定的任务上苦苦挣扎了将近一个星期，但没有成功找到解决方案，所以这个网站是我最后的希望。

我有0-1 背包问题，其中有 20 个具有不同值和重量的物品，麻袋的最大重量是 524。现在我需要实施蛮力来找到 20 个物品的最佳解决方案子集，以便总重量 <= 524 和最大值选择的项目。

您能否指出我或更好地给出详细的实现来分析它是如何工作的！非常感谢

我遇到了思维问题，我很沮丧。我有一个背包问题的工作算法，使用动态编程，我在其中指定

• 最大负荷
• 物品（重量）

该算法使用这些物品计算背包的最佳填充量。但是现在我需要完全填充它，使用最少的项目，但我每个项目的数量都是无限的。（这些项目有重量{1; w1; w2; ...}，所以总是可以完成）。

我如何在“经典”算法中适应这个？

谢谢