贪心算法

创建时间 2021-10-11

更新时间 2021-10-11

分类

计算机科学

标签

算法

分数背包问题

贪心选择性质的证明

设 $I$ 为背包问题，其中设：

设 $S = (s_1, s_2, \cdots, s_n)$ 为一个解，贪心算法假设 $s_n = \min(w_n, W)$ ，然后继续求解子问题

$I' = (n - 1, \{v_1, v_2, \cdots, v_{n - 1}\}, \{w_1, w_2, \cdots, w_{n - 1}\}, W - w_n)$

直到达到 $W = 0$ 或 $n = 0$ 的状态

我们需要证明这种策略总会给出最优解，我们利用反证法来证明这一点；

假设 $I$ 的最优解是 $s_1, s_2, \cdots, s_n$ ，其中 $s_n < \min(w_n, W)$ ，设 $i$ 是使 $s_i > 0$ 的最小的数，通过减少 $s_i$ 到 $\max(0, W - w_n)$ 同时增加 $s_n$ 相同的量，

我们的到了一个更好的解；这是一个矛盾，所以假设是错误的，因此这个问题具有贪心选择性质。