题解 P1094 【纪念品分组】

heidoudou

2018-08-10 23:41:24

题解

贪心算法并不难,难的是证明。 --- 杨科洛夫斯基(heidoudou)

贪心算法:先对数组从小到大排序,用 i = 1, j = n 指针指向首尾元素; 如果 a_i + a_j > w ,则将 a_j 单独作为一组,指针j-- ;如果 a_i + a_j \leq w, 则将 a_ia_j 分为一组, 指针 i--, j--。 如此重复直到 “取完” 所有元素。

贪心算法证明: 对于 a[i...j] 问题,如果存在最优解 S,但是 a_ia_j 的分组不符合上述贪心选择过程。会有以下几种情况:

  1. 如果 a_i + a_j > wa_j 也不可能与其他任何 a_ki < k < j 一组。 a_j 只能单独一组。这是符合贪心选择性质的。
  2. 如果 a_i + a_j \leq w, 在最优解中,a_j 并不与 a_i 一组,
    1. a_j$ 与 $a_k$ 一组,$a_i$ 单独一组,交换 $a_i$ 和 $a_k$, 不难看出 $S' = S

至此,我们证明了问题的某个最优解可以通过上述贪心选择过程得到。

下面证明 贪心选择加子问题的最优解 为全局最优解。

设有 a[i...j]问题(记为 P)的贪心解为 S, 经过贪心选择之后 子问题 P' 的最优解为 S'。 如果贪心选择加子问题 的最优解S' 不是 P 的最优解。 假设存在一个最优解 Z, 可以通过上面的证明过程,改变解的结构,使之变成一个贪心选择和相同子问题 P' 的解 Z'。 因为 S > Z,并且二者贪心选择所产生的分组数是相同的,所以 S' > Z', 这与 S' 是最优解矛盾。所以贪心选择加子问题的最优解 为全局最优解。

证毕。

写的啰嗦了一点, 但是读懂这些证明以及为什么这样证明对理解贪心算法大有裨益。

光知道贪心,贪心为什么可以得到最优解,你证明过么?