如何计算找到这种松弛。我应该知道什么才能找到它。假设我有 n 个物品和 m 个背包。所以我想知道 m 放松的数量。有没有人至少可以给我一些想法。我一直在寻找它。网上有一些文章，但不是很清楚。请至少有人对我说你应该读这个东西，你应该知道这个东西，所以我会非常感激
谢谢
问问题
1344 次
1 回答
1
我认为您真正的问题是“线性松弛背包问题的确切定义是什么？”，所以我假设是这样回答。
简短的回答是线性松弛KP 是 0-1 KP [1] 的分数版本。
在数学上，你所要做的就是将限制“x_i 属于 {0, 1} 集合”转换为“x_i 必须是 0 到 1 之间的任何实数”，其中 x_i 是 i-解决方案背包中的物品。
这个名字来源于 0-1 KP 是一个整数规划问题。“线性”术语意味着解决方案变量可以采用连续值。
不过，并非所有的松弛都是线性的。您可能想为他们查看此Wikipedia 页面。
[1] http://en.wikipedia.org/wiki/Linear_programming_relaxation
于 2011-06-23T13:17:21.620 回答