如何证明分数背包表现出贪心策略。？

Question

我如何证明分数背包表现出贪心策略，

我可以实践，但我找不到理论上证明它的方法。？

请帮忙提前致谢

Answer 1

（原始）分数背包 LP 是

maximize sum_{i=1}^n v_i x_i
subject to
y: sum_{i=1}^n w_i x_i <= W
z_i: x_i <= 1  (for i=1 to n)
x_i >= 0  (for i=1 to n),

其中v_i是项目i的价值，w_i是权重。双LP是

minimize W y + sum_{i=1}^n z_i
subject to
x_i: w_i y + z_i >= v_i
y >= 0
z_i >= 0  (for i=1 to n).

通过（弱）LP 对偶性，如果原始的贪婪解与对偶的解具有相同的 objective，则两者都是最优的。假设所有权重都是正数，它们的总和大于 W，并且商品的排序使得 v_1/w_1 >= v_2/w_2 >= ... >= v_n/w_n。设j为枢轴项，则贪心原始解为

x_1, x_2, ..., x_{j-1} = 1
x_j = (W - sum_{i=1}^{j-1} w_i) / w_j
x_{j+1}, x_{j+2}, ..., x_n = 0.

通过互补松弛，我们可以猜测，在对偶中，我们应该有

z_j, z_{j+1}, ..., z_n = 0.

对偶中的x_i约束等同于

y + z_i/w_i >= v_i/w_i,

所以我们需要设置

y >= v_j/w_j >= v_{j+1}/w_{j+1} >= ... >= v_n/w_n

为了满足我们置零的约束 z_i。凭直觉，我们设置

y = v_j/w_j,

直观地强制赋值

z_i = (v_i/w_i - v_j/w_j) w_i  (for i=1 to j-1).

现在是这个论证中唯一需要严格的部分：验证这是对偶的可行解决方案（乏味，因此留作练习）并且 objective 与贪婪的原始匹配解决方案。 objective 是

W y + sum_{i=1}^{j-1} z_i =
W (v_j/w_j) + sum_{i=1}^{j-1} (v_i/w_i - v_j/w_j) w_i =
sum_{i=1}^{j-1} (v_i/w_i) w_i + (v_j/w_j) (W - sum_{i=1}^{j-1} w_i) =
sum_{i=1}^{j-1} v_i + ((W - sum_{i=1}^{j-1} w_i) / w_j) v_j,

这确实是原始的objective。

Answer 2

我们需要证明这个问题有贪心的选择属性。为此，我们需要证明任何不包含贪心选择 a 的解决方案 X 在与 a.[=23= 交换某些选择后不会得到更差的解决方案]

对于分数背包，这很容易证明：我们取 X 的任何元素，比如 b。如果w_a >= w'_b（其中w_a是a，而 w'_b 是 b 在解 X 中的权重，我们可以将 b 替换为 b 的大部分 a 尽可能。因为 a 是值密度最大的项目（这是我们的贪心选择），这不会使解决方案变得更糟。如果 w_a < w'_b 我们可以取所有 a，并使 w'_b = w'_b - w_a。同样，因为 a 具有最大的值密度，这不会使解决方案变差。

就是这样！从技术上讲，我们还需要展示最佳子结构，但这对于这个问题来说应该是相当简单的。

如何证明分数背包表现出贪心策略。？

How to prove that Fractional Knapsack exhibits Greedy Strategy.?

algorithm

knapsack-problem