问题标签 [knapsack-problem]

我有一个表面上看起来像0-1背包的问题。我有一组可以选择（或不选择）的可能“候选人”，每个候选人都有一个“权重”（成本）和一个潜在的“价值”。如果这是整个问题，我会使用 DP 方法并完成它。但这是曲线球：最终解决方案中可能存在的候选对象存在“分区约束”。

我的意思是候选空间被分成离散的等价类。对于我的特定问题，大约有 300 个候选人和 12 个可能的等价类。有“商业规则”说我最多只能说 C1 班的 3 名候选人和 C2 班的 6 名候选人，等等。

这个约束建议使用分支定界技术或其他形式的剪枝的图搜索类型方法，但是我对如何开始有点困惑，因为我只熟悉 0-1 背包的 DP 解决方案。什么技术/方法可能适合这个问题？我也想过可能使用约束编程库，但不确定它是否能够找到解决方案？

我正在上我的第一门编程课程，现在我很困惑。基本上，我们所做的是从文本文件（在第一行代码）中获取 16 个值，在第二行代码中只有一个值。我们将这 16 个值读入一个数组，并将第二行值设置为目标。我对那部分没有问题。

但是，我遇到麻烦的地方是创建一个位图来测试 16 个值的每个可能的子集，它等于目标数。

IE，假设我们有这些数字：

然后我们将每个值对应一个位图

那么我们只接受以“1”为谓词的值

然后我们测试该子集以查看它是否等于“目标”数。

我们只允许在问题中使用一个数组，并且我们不允许使用数学类（还没有得到它）​​。

我理解这个概念，我知道我需要实现移位运算符和逻辑&符号，但我真的很茫然。我非常沮丧，我只是想知道是否有人可以给我任何提示。

我已经用 Scala 中的每个项目写了一个有界背包问题的答案，并尝试将其转换为 Haskell，结果如下：

我不是在寻找关于如何清理代码的提示，只是为了让它工作。据我所知，它应该执行以下操作：

• 对于每个元组选项（在 ys 中）
  • 如果当前元组 (y) 和运行总和 (xs) 组合的权重小于容量
  • 使用可用的元组（以 ys 为单位）减去当前元组，得到包含当前元组和当前总数 (xs) 的最佳背包
• 最后，获取这些结果中最有价值的并返回

*编辑：*对不起，忘了说什么是错的......所以它编译好了，但它给出了错误的答案。对于以下输入，我期望什么以及它产生什么：

所以我想知道差异的原因可能是什么？

解决方案，感谢 sepp2k：

上面返回预期结果。

我必须写一个背包问题的蛮力实现。这是伪代码：

虽然该算法相当容易实现，但我一点也不知道如何生成 S 的幂集，以及如何将幂集的子集输入到 while 循环的每次迭代中。

我当前的实现使用一对列表来保存项目的重量和利润：

我想为我的 computeMaxProfit 函数生成这个列表的幂集。是否有一种算法可以生成列表的子集？列表是正确的容器吗？

维基百科关于背包问题的文章包含三种类型：

1. 1-0（一种类型的一项）

2. 有界（一种类型的几个项目）

3. Unbounded（一种类型的项目数量不限）

该文章包含针对 1. 和 3. 类型问题的 DP 方法，但没有针对 2. 的解决方案。

如何描述求解 2. 的动态规划算法？

我在求和问题的递归解决方案中遇到问题。问题是：对于给定的 m 和 n，编写一个程序，将 n 个数字加总为 m，以便使用最小数字并且它们是。Id 有多个解决方案，正确的一个是使用更大数字的那个。用户输入 n,m 和 n 个数字。例如： m=19 n=4 8,5,4,1 。解决方案是 8+5+5+1。如果我用数组中的下一个数字调用函数并在其小于 sum 时添加它，则只有当数组中的下一个数字总和为 m 时才会找到解决方案。如果问题是这样的： m=28 n=3 8,7,5 解决方案是 8+8+7+5 但我的程序会去 8+8+8 并尝试添加 7 或 5 会崩溃，因为没有其中最多可以容纳 28 个。所以我在这里的问题是返回超过 2 个步骤。我可以从 8+8+8+7 到 8+8+8 但不能回到 8+8。这类似于背包问题，只是它更简单。抱歉到目前为止没有包括我的代码：

输出有问题，但现在这并不重要。

我在理解动态编程方面遇到了困难，所以我决定解决一些问题。我知道基本的动态算法，如最长公共子序列、背包问题，但我知道它们是因为我读过它们，但我自己无法想出一些东西:-(

例如，我们有自然数的子序列。我们可以用加号或减号取的每个数字。最后我们取这个总和的绝对值。对于每个子序列，找到可能的最低结果。

in1：10 3 5 4；输出1：2

in2：4 11 5 5 5；输出2：0

in3：10 50 60 65 90 100；输出3：5

第三个解释：5 = |10+50+60+65-90-100|

更糟糕的是我的朋友告诉我这是简单的背包问题，但我在这里看不到任何背包。动态编程是困难的还是只有我有大问题？

我搜索了这种类型的算法并红色了很多东西，但我找不到我正在寻找的东西。

所以，我要去购物，我有 x 的钱，我的卡车最多可以承受 y 的重量，而且每件商品都有一个奖励积分、一个重量和一个价格。输出应该给出可以获得的最大奖励积分，以使所选物品的总重量不超过卡车的容量和我必须花费的钱！

我可以在这里使用一些帮助，你知道算法的名称吗？我应该如何进行？我必须用C来做！

谢谢 ！！

我制作了一个 prolog 程序，向我展示了在 dvd 上安装内容的最佳方式。问题在代码的注释中以供参考，我将在下面粘贴，但归结为：

1. 是否有一种倒切运算符可以让它搜索更多，尽管它已经匹配？参见 fitexact，类似于 fitexact(Size,Sum,L,L):-Sum

2. 跟踪已处理电影的最佳方式是什么？我收回它们，但想知道没有它怎么做。

3. fitfuzzy 使用一个if then构造。我不知道该怎么想他们，在序言中感觉很奇怪。然而，试图使其递归让我非常困惑:)

我认为这可能是多重背包问题的一种变体（或者甚至可以简化为它），但我不确定。这是问题所在：

您有一组具有已知值和权重的项目。你还有一套背包，每个背包可以装固定数量的物品（不同的背包可能能装不同数量的物品）。在保持在给定重量下的情况下，最大化背包中物品的总价值。

请注意，单个背包没有重量限制。每个背包只有一个“它可以包含的物品数量”的限制。唯一的其他限制是物品的总重量。

有任何想法吗？？（当然除了蛮力）。提前致谢！:)

编辑：我忘记包括的一个重要限制：

物品不一定要放在任何袋子里。本质上，如果将它们放入不兼容的袋子中，它们的价值就会变为零。您可以想象一个一般情况，其中每个项目的值取决于其包，但在我的情况下，它的值将是 0 或正常值，具体取决于包。