题解 P1094 【纪念品分组】

· · 题解

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

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

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

  1. 如果 a_i + a_j > w，a_j 也不可能与其他任何 a_k， i < k < j 一组。 a_j 只能单独一组。这是符合贪心选择性质的。
  2. 如果 a_i + a_j \leq w， 在最优解中，a_j 并不与 a_i 一组，
    3. 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' 是最优解矛盾。所以贪心选择加子问题的最优解 为全局最优解。

证毕。

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

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