我愿称贪心算法为贪婪鼠目寸光#xff0c;贪心算法#xff08;Greedy

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

Algorithm是把求解的问题分成若干个子问题在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的算法。

贪心算法并不保证总能找到全局最优解但在许多情况下它能够产生很好的结果并且实现简单效率高所以是“希望”得到最优解

1贪心策略的提出是没有标准与模板的即根据问题的具体情况选择一种贪心策略以求解每一步的最优解。

但是针对不同的分成子问题的方法又有不同的策略。

2贪心策略的正确性是需要证明的即证明采用贪心策略能够得到问题的整体最优解。

这通常通过数学归纳法、反证法或构造法来证明。

经典问题

种硬币或纸币的面值。

目标是找到一种使用这些硬币或纸币组成目标金额

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

因为20是10的二倍那B就有三情况B2,B2,B2,因为B2时那变成了A,所以B1,同理c1,d4.

故aA因为aA的话那剩余的数达不到20,105419注意是在最优解的情况下。

因为aA的话那b可能1,c可能1,d可能4故aAbB,cC,dD

二背包问题

定一个背包背包有一个最大承重限制以及一组物品每个物品都有自己的重量和价值。

要求选择部分物品装入背包使得背包中的物品总价值最大同时不超过背包的最大承重限制。

解题思路

排序首先将所有物品按照它们的单位价值即价值除以重量从高到低进行排序。

单位价值越高的物品我们越希望尽可能多地装入背包。

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

计算总价值重复上述过程直到所有物品都被考虑过或者背包已满。

最后计算背包中所有物品的总价值。

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

步骤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的最短路径。

这一性质保证了在求解最短路径时可以局部地做出最优选择而这些局部最优选择最终能组合成全局最优解。

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