问题标签 [knapsack-problem]

我有 I1、I2、I3、I4 项，权重为 W1...W4，值 V1...V4。我想用最小的权重最大化值。这是一个传统的背包。然而，有些项目不能放在一起有一个小的限制。因此，可以说 I2 和 I3 不能一起使用。任何人都可以提供动态编程解决方案或任何其他解决方案。

我编写了一个用于生成子集总和的程序，该程序可用于此问题，其中指出：

假设你有 3 个 1 美元硬币、2 个 2 美元硬币、3 个 5 美元硬币、1 个 10 美元硬币，有 4 种方法可以从这些硬币中获得 10 美元。如果有 n1 个 $X1 个硬币，n2 个 $X2 个硬币...... nm $Xm 个硬币，我们有多少种方法可以从这些有限数量的硬币中获得 $X？

如果我们创建一组 { X1, X1..... X1, X2, X2.......... X2, ..., ..., .... .., Xm, Xm... Xm}，然后对它运行子集求和，当然我们可以得到 $X 的结果。但我找不到使用集合 {n1, n2, n3.... nm} , {X1, X2, X3.... Xm} 的方法。一位朋友告诉我，这是背包问题的变体，但我不确定如何。

这是我写的部分代码：

如果您能详细解释一下，那对我来说会很棒。

编辑：这个问题更适合用于计算机科学的 stackexchange，但由于这是我的一个老问题，我宁愿在这里编辑它。

这个问题可以通过包含排除原则来解决，当我们将硬币值固定但每个硬币的数量随每次查询而变化时，它会派上用场。

假设，ways[v]是用$x1，$x2， .. $xm制作$v的方法，每个都可以根据需要多次使用。现在，如果我们只使用n1个$x1数字，我们必须使用至少 ( n1 + 1) 个$x1数字减去配置（这实际上是方式[ v - (n1 + 1)x1 ] ）。此外，如果我们只使用$x2的n2个数字，我们还必须减去方式[ v - (n2 + 1)x2 ]，等等。

现在，我们已经两次减去至少使用 ( n1 + 1) $x1和 ( n2 + 1) $x2的配置，因此我们需要添加方式[ v -(n1 + 1)x1 - (n2 + 1) x2 ] 等。

特别是，如果，

N = 尽可能多地使用所有硬币的一组配置，

Ai = 至少使用ni + 1 个$xi的配置集，对于 1 <= i <= m，则

我们正在寻求的结果 = | N | - | A1 | - | A2 | .. - | 上午| + | A1和A2 | + | A1和A3 | + ... - | A1和A2和A3 | ......

计算无限硬币配置数量的代码实际上更简单：

我一直在尝试自学如何使用 JaCoP 约束编程库，但在实现 0/1 背包问题时遇到了一些困难。我尝试了 4 的问题大小并定义了项目和变量，如下所示：

然后我使用背包列表添加了一个背包约束：

约束 con = new Knapsack(knapsack, knapsackCapacity, knapsackProfit); store.impose(con);

然后我按照教程中给出的方式搜索了解决方案：

我得到的结果很简单，所有数量都为零，这满足了约束但没有优化任何东西。是否还有其他约束或我应该添加的东西来尝试最大化每个项目的利润*数量？

谢谢

本

当所有利润都等于 1 时，背包问题有一个变体。它似乎可以比经典离散 (0-1) 背包问题更快地解决，但是如何解决呢？贪心算法会起作用吗（在每次迭代中将一个重量最小的物体放在背包上）？

This is a hard algorithms problem that :

Divide the list in 2 parts (sum) that their sum closest to (most) each other

list length is 1 <= n <= 100 and their(numbers) weights 1<=w<=250 given in the question.

For example : 23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

I have an algorithm but it didn't work for all inputs.

1. init. lists list1 = [], list2 = []
2. Sort elements (given list) [23 32 34 65 95 123 134]
3. pop last one (max one)
4. insert to the list which differs less

Implementation : list1 = [], list2 = []

1. select 134 insert list1. list1 = [134]
2. select 123 insert list2. because if you insert to the list1 the difference getting bigger
   3. select 95 and insert list2 . because sum(list2) + 95 - sum(list1) is less.

and so on...

我正在开发一款游戏，但我发现了一个问题，我必须解决这个问题来处理类似于我的包装问题的组件布局。

总结一下我需要做的事情，假设我有一个类似于以下空间的空间：

其中每个角落单元格是 4x4，而中央单元格是 3x3（因此剩余的单元格是 3x4 和 4x3）。然后我有一组元素放置在这些块中，这些块可以从 1x1 到 3x3 不等（我认为还不需要任何 4x4，但它不应该改变任何东西）。当然，这些元素不能越界，必须完全放在一个块内。

哪一种可能是分配它们的最佳方式？假设如果没有必要，我不希望将它们全部粘在一起（例如，如果周围有足够的空间将它们分开，则不要将两个元素放在一起）。我正在寻找一个简单的算法，也是因为情况非常有限..

奖励问题：假设除了这 9 个（可能是其他 3-4 个）之外的其他块，与新块相比，我如何优先考虑这些块？（我的意思是在达到填充阈值之前不使用附加块）..

当然我正在寻找一般的想法，没有实现:)

我知道这Knapsack是 NP 完全的，而 DP 可以解决它。他们说 DP 解决方案是pseudo-polynomial，因为它是“输入长度”的指数（即编码输入所需的位数）。不幸的是我没有得到它。谁能pseudo-polynomial慢慢给我解释一下？

我知道如何使用动态编程方法解决背包 0-1 问题，但是在不影响 O(N * C) （N 个项目，C 容量）的复杂性的情况下确定要采取哪些项目时遇到了麻烦。

有什么想法（我更喜欢自下而上的方法）？

给定一组项目（大小从 1 到 100 的任意位置）和一些箱（1 到 15）。每个项目都有一个箱子集，该项目可以分配到，以及哪个箱最好、次佳、等等，只是为了它。项目也有自然顺序，下面用命名来表示，例如，项目 1 在项目 2 之前。每个箱子的容量在 1 到 5 之间（每个物品的重量相同，即 1。）

示例输入可以是三个箱子和六个物品（- 表示箱子不在物品的可用集合中，即不能与它一起打包）：

目标是（为了在发生冲突时每个目标完全覆盖任何较低的目标，例如，无论使用多少箱或忽略偏好，打包五个物品总是优于四个）：

1. 最大化包装的物品数量
2. 按自然顺序包装物品，例如，如果总箱容量为 1 并且有两个物品，则将包装 item1 而 item2 不包装
3. 最小化使用的垃圾箱数量
4. 根据每个项目的 bin 偏好和自然顺序打包每个项目，即第一个偏好中的 item1 和第二个中的 item2 优于第二个中的 item1 和第一个中的 item2
5. 在两个解决方案无法通过这些目标区分的情况下，任何一个解决方案都可以接受更高的排名，例如，作为实施的副作用或只是任意的平局。

所以上面的输入将被打包为：

然后的问题是阅读/审查什么来帮助我想出解决这个问题的算法想法，第一段的输入大小和几秒钟的时间限制，即不是蛮力（或至少任何蛮力到目前为止我已经想到的力量。）我正在使用 Ruby 和 C，但是在这个林木蹒跚的阶段，语言并没有过度相关。

我将不胜感激任何阅读建议、关于算法组合的想法，或者只是关于澄清问题陈述的想法......

更新 1

不太清楚，虽然有许多算法涵盖了这方面的各个部分，但我的困难在于找到（或可能识别）一起处理所有标准的信息，特别是在容量过剩和项目冲突时尽量减少使用的垃圾箱数量-bin 设置和项目偏好，希望在以下示例中更清楚地显示：

虽然 bin1 是最首选的，但 item3 根本不能放在其中，而 bin2 是所有项目的第二首选，它只能容纳三个项目中的两个。所以正确的赋值集 (x) 实际上是最不喜欢的 bin：

更新 2 我用有关目标如何关联的信息重新编写了描述，并删除了 bin 优先级变量，因为它只会降低找到答案的可能性，并且可以在我正在处理的系统的其他地方解决。

我的回溯函数有问题，它会循环某些数据，我不能在这里写整个程序代码，但可以把我的函数放在这里。

现在解释一下：

quantity - values
中 的 元素
数指数组值

该函数获取长度为 values 数组的元素的数量，values 一个包含数字的数组，从最高到最低排序，索引控制递归，默认为 0，因此它从第一个元素开始，moneyA 存储数字的变量值数组，它应该达到一半，这是从值数组求和的数字的一半，并且 ifChosen 存储选择的数字。

整个函数执行此操作，它对 values 数组中的元素求和并检查它是否达到一半，如果它低于一半，则将其添加到 moneyA 并在 ifChosen 中标记，然后它转到下一个，如果总和高于它的一半取回并在 ifChosen 数组中取消标记它并从 moneyA 中减去。它应该总是得到最高的元素。

这是一个简单的例子：

这个结果应该是：

当然，对于这个简单的示例，它做得很好，但是对于具有更多数字并且一个数字不止一次出现的更复杂的示例，它循环并且递归永远不会停止。我实际上已经为此工作了 1.5 周，并询问了我所有的朋友，但没有人知道它有什么问题。我知道这与背包问题有点关系，但我还没有那个问题，仍然需要学习。

我期待任何可以提供帮助的答案。

我很抱歉我的标点符号，但我是第一次来这里，不习惯格式化。

这里有一个例子：

现在我认为它会永远循环：43 个元素：

@Karl Bielefeldt 是的，我知道有很多组合，这就是我试图加快速度的原因。现在这就是我所得到的，但它给我某些输入的错误结果。任何人都可以纠正它，它比以前工作得更快吗？