题解 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$ 一组， 1. $a_j$ 单独一组，这时候如果最优解的 $a_i$ 仍然孤单， 那么将他俩合为一组，最优解的分组数减一，居然优于最优解，矛盾。 2. $a_j$ 单独一组， $a_i$ 与另一个 $a_k$ 一组，这时候，将 $a_i$ 从 $a_k$ 身边拆开，再与 $a_j$ 一组，所得分组数不变，新的解 $S' = S$，$a_i$ 和 $a_j$ 一组是符合贪心选择性质的，贪心选择可以得到最优解。 3. $a_j$ 与 $a_k$ 一组，$a_i$ 单独一组，交换 $a_i$ 和 $a_k$， 不难看出 $S' = S$ 4. $a_j$ 与 $a_k$ 一组， $a_i$ 与 $a_m$ 一组，交换 $a_k$ 与 $a_i$ 之后， $a_i + a_j \leq w$， $a_k + a_m \leq a_k + a_j \leq w$， $S' = S$， 至此，我们证明了问题的某个最优解可以通过上述贪心选择过程得到。 下面证明 贪心选择加子问题的最优解 为全局最优解。 设有 `a[i...j]`问题（记为 $P$）的贪心解为 $S$， 经过贪心选择之后 子问题 $P'$ 的最优解为 $S'$。 如果贪心选择加子问题 的最优解$S'$ 不是 $P$ 的最优解。 假设存在一个最优解 $Z$， 可以通过上面的证明过程，改变解的结构，使之变成一个贪心选择和相同子问题 $P'$ 的解 $Z'$。 因为 $S > Z$，并且二者贪心选择所产生的分组数是相同的，所以 $S' > Z'$， 这与 $S'$ 是最优解矛盾。所以贪心选择加子问题的最优解 为全局最优解。 证毕。 写的啰嗦了一点， 但是读懂这些证明以及为什么这样证明对理解贪心算法大有裨益。 光知道贪心，贪心为什么可以得到最优解，你证明过么？