1

古老而著名的背包问题要求给定容量 C 和包含 n 个项目 {I_1, I_2,..., I_n} 且每个 I_j=(weight_j, value_j) 的列表，尝试在装满背包的同时最大化价值.

但是如果我们添加一个约束会发生什么

1) 选择特定项目的次数必须为 0 或必须为奇数（例如：只能不带 10 磅哑铃或 1、3、5、.. 数量）。2) 对于所有 j，C = n^2 和 n <= weight_j <= n^2。

可以使用哪些动态规划实现来处理额外的约束？

一些关于如何开始的建议将不胜感激。谢谢！

4

2 回答 2

1

您可以将背包问题的这种变体表示为整数程序

标准背包问题：

 Maximize sum(j) Value_j x X_j
 subject to
         sum(j) Wt_j x X_j <= C
         X_j is integer

在您的变体中，X_j 只能采用不同的值：{0, 1,3,5,...}

制定约束以限制 X 取奇数值

每当变量可以采用的值存在这些类型的限制时，引入 0/1 变量来处理这些条件。

对于每个项目j，让我们引入一堆二进制Y变量和几个新约束。

X_j - 1 Y_j1 - 3 Y_j3 - 5 Y_j5 ... - M Y_jm = 0

m 是 Xj 可以取的最大值（奇数）。

为了限制 X_j 假设这些值之一，我们添加

Y_j0 + Y_j1 + Y_j3 + ... + Y_jm = 1 for each item j
Y_j0, Y_j1, Y_j3 ..., Y_jm are {0,1} (binary)

变量 Y_j0 是为了让 X_j 取值 0。

这一事实确保我们可以为每个约束C = n^2提出合理的上限。m

您现在可以使用整数规划求解器求解这个修改后的背包。它仍然会按“价值密度”（每公斤价值）的递减顺序查找项目，而将其限制为奇数值的约束将在某些边界条件下生效。

希望有帮助。

于 2013-07-02T21:27:52.707 回答
0

背包问题是一个整数规划问题，最简单的形式可以通过动态规划来解决。即使对问题进行看似很小的更改也会使其变得更加困难并且更适合其他方法。最直接的方法是将其放松为多个线性程序，同时使用分支并通过可行的解决方案进行工作。也可以使用切割平面 - 但人们通常会发现它更容易理解和实施分支和绑定。看看这里http://mat.gsia.cmu.edu/orclass/integer/integer.html（更简单，更容易访问）http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf（更完整）

于 2013-07-01T22:47:12.247 回答