自动搬运

查看原文

来自洛谷，原作者为

	heidoudou **

搬运于2025-08-24 21:20:51，当前版本为作者最后更新于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_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'$ 是最优解矛盾。所以贪心选择加子问题的最优解 为全局最优解。

证毕。

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

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