如何计算找到这种松弛。我应该知道什么才能找到它。假设我有 n 个物品和 m 个背包。所以我想知道 m 放松的数量。有没有人至少可以给我一些想法。我一直在寻找它。网上有一些文章,但不是很清楚。请至少有人对我说你应该读这个东西,你应该知道这个东西,所以我会非常感激
谢谢
如何计算找到这种松弛。我应该知道什么才能找到它。假设我有 n 个物品和 m 个背包。所以我想知道 m 放松的数量。有没有人至少可以给我一些想法。我一直在寻找它。网上有一些文章,但不是很清楚。请至少有人对我说你应该读这个东西,你应该知道这个东西,所以我会非常感激
谢谢
我认为您真正的问题是“线性松弛背包问题的确切定义是什么?”,所以我假设是这样回答。
简短的回答是线性松弛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