贪心算法

创建时间 2021-10-11
更新时间 2021-10-11

分数背包问题

贪心选择性质的证明

I 为背包问题,其中设:

  • n 为其中物品的数量
  • v_i 为第 i 个物品的价值
  • w_i 为第 i 个物品的重量
  • 物品以 v_i/w_i 递增排序
  • W > w_n 为背包的容量

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 = 0n = 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 相同的量,

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


参考引用

  • 《算法导论》