My Greedy Algorithm（贪心算法）之路（一）

引子：我们之前，其实也遇到过贪心算法，0,1背包就是一个典型的贪心算法问题，那今天我就来开始my-Greedy Algorithm的道路。

什么是贪心算法？

我愿称贪心算法为贪婪+鼠目寸光，贪心算法（Greedy Algorithm）是把求解的问题分成若干个子问题，在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法并不保证总能找到全局最优解，但在许多情况下，它能够产生很好的结果，并且实现简单，效率高，所以是“希望”得到最优解！

贪心的特征

总结以下二点：

1，贪心策略的提出：是没有标准与模板的！即根据问题的具体情况，选择一种贪心策略，以求解每一步的最优解。但是，针对不同的分成子问题的方法，又有不同的策略。

2，贪心策略的正确性：是需要证明的！即证明采用贪心策略能够得到问题的整体最优解。这通常通过数学归纳法、反证法或构造法来证明。

经典问题；

一，找零问题

 给定一个目标金额 N 和一个硬币（或纸币）的集合 C = {c1, c2, ..., cm}，其中 ci 是第 i 种硬币（或纸币）的面值。目标是找到一种使用这些硬币（或纸币）组成目标金额 N 的方式，使得使用的硬币（或纸币）数量最少

证明：策略的正确性

假设有以下零钱：{20,10,5,1}

那我们假设最优解对应的个数是{A,B,C,D},我们贪心得到的个数为{a,b,c,d}.

因为20是10的二倍，那B就有三情况，B>2,B=2,B<2,因为B>=2时，那变成了A,所以，B<=1,同理，c<=1,d<=4.

故a>=A，因为a<A的话，那剩余的数达不到20,10+5+4=19（注意是在最优解的情况下）。

因为a>A的话，那b可能>1,c可能>1,d可能>4，故a=A，b=B,c=C,d=D

二，背包问题

定一个背包，背包有一个最大承重限制，以及一组物品，每个物品都有自己的重量和价值。要求选择部分物品装入背包，使得背包中的物品总价值最大，同时不超过背包的最大承重限制。

解题思路

1. 排序：首先，将所有物品按照它们的单位价值（即价值除以重量）从高到低进行排序。单位价值越高的物品，我们越希望尽可能多地装入背包。

2. 贪心选择：从单位价值最高的物品开始，尝试将其装入背包，直到达到背包的容量限制或该物品被完全装入背包。

3. 计算总价值：重复上述过程，直到所有物品都被考虑过，或者背包已满。最后，计算背包中所有物品的总价值。

证明：策略的正确性

假设：存在一种不同于上述贪心策略的方法，能够产生更高的总价值，同时不超过背包的最大承重限制。

步骤1：考虑这种假设下的最优解，它必然包含了一系列的物品选择及其对应的重量分配（可能是部分分配）。

步骤2：假设在这个最优解中，存在某个物品A，其单位价值并不是当前未被选中的物品中单位价值最高的。那么，我们可以找到至少一个未被选中的物品B，其单位价值高于物品A。

步骤3：由于背包问题允许物品分割，我们可以尝试将物品A从背包中完全移除（如果它是部分添加的，则移除其已添加的部分），并用相同重量的物品B来替代。由于物品B的单位价值更高，这种替换将增加背包中的总价值，而不改变背包的总重量。

步骤4：重复上述步骤，对于最优解中所有单位价值不是最高的物品，都尝试用单位价值更高的物品来替换。这样，我们可以构造出一个新的解，它的总价值高于原始的最优解，这与我们的初始假设（原始解是最优的）相矛盾。

结论：因此，我们的假设是错误的，即不存在一种不同于贪心策略的方法能够产生更高的总价值。所以，贪心策略（按单位价值从高到低排序，并尽可能多地装入背包）是正确的。

注意

• 这个证明依赖于背包问题允许物品分割的特性。在不允许分割的0-1背包问题中，贪心策略并不总是有效的。
• 证明中的“替换”操作是基于物品可以分割的假设，这意味着我们可以选择性地添加或移除物品的部分重量，而不是整个物品。
• 这个证明也说明了贪心算法在解决分数背包问题时的有效性和最优性。

三，最短路径问题

贪心算法在求解最短路径问题时，通常采取的策略是逐步扩展已知的最短路径，每次选择当前可达的、且距离起点最近的顶点进行扩展。这种策略基于贪心选择性质，即每一步都选择当前看来最优的解（即距离起点最近的可达顶点），并期望通过这些局部最优选择达到全局最优解。

最短路径问题具有最优子结构性质，这是采用贪心算法解决问题的关键特征。该性质描述为：如果P(i,j)={Vi...Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。这一性质保证了在求解最短路径时，可以局部地做出最优选择，而这些局部最优选择最终能组合成全局最优解。

还有很多的例子与问题，我们下次从题目入手！，感谢大家与我一起进入贪心算法的课程，下次，我也会开始优选算法的道路！