百度做一个网站怎么做呢,餐饮vi设计案例,设计有限公司,wordpress 淘宝客 百度贪心算法简介 1.什么是贪心算法2.贪心算法的特点3.学习贪心的方向 点赞#x1f44d;#x1f44d;收藏#x1f31f;#x1f31f;关注#x1f496;#x1f496; 你的支持是对我最大的鼓励#xff0c;我们一起努力吧!#x1f603;#x1f603; 1.什么是贪心算法
与其说是… 贪心算法简介 1.什么是贪心算法2.贪心算法的特点3.学习贪心的方向 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1.什么是贪心算法
与其说是贪心算法不如说是贪心策略。
贪心策略解决问题的策略( 局部最优 — 全局最优)。
把解决问题的过程分为若干步解决每一步的时候都选择当前看起来 “最优的” 解法“希望” 得到全局最优解。
接下来我们举三个例子重点突然我们的贪心策略。 例一找零问题 假设顾客拿着50块钱去买一瓶4块钱的饮料你需要找顾客46块钱。此时你只有面额20元、10元、5元、1元 若干个纸币。我们要的是用最少的张数完成找零。
我给你找46块钱肯定是一张一张给你凑成46块钱。解决问题的时候整个问题就分为若干步若干步就是一张一张的给你找。然后解决每一步的时候都选择当前看起来 “最优的” 解法。
当开始凑46块钱的时候刚开始肯定不会拿最小的1块钱我想的是最少的张数那应该是最快的凑够46块钱。所以第一次肯定选择20块。接下来在凑26块钱然后凑26块钱我依旧选择当前看起来最优的还是20块钱。接下来凑6块钱20和10就不要考虑了然后选5块钱接下来在选1块钱最后正好可以凑够46块钱。 回顾找零过程非常符合贪心策略每次找钱都选择当前能选择的最大面额选择u最大面额就能用最少的张数凑成46块钱。 例二最小路径和 我们在动态规划遇到这道题。我想从左上角到达右下角然后每次走只能向下走或者向右走。每个格子都是路径问从左上角达到右下角最小路径和是多少 这里已经把问题拆分若干个了从起点一步一步走就是。每一步走的时候都选择当前看起来 “最优的” 解法。从左上角开始走最终走到右下角贪心路径和是10 。 但是可能会有个异或这个10好像不对我们直接观察最小的路径和是7。现在先不管正确解法是什么我们先搞懂什么是贪心策略。 例三背包问题 物品编号从1~3每个物品都有体积和价值。此时你手里还有一个最大容量为8的背包。每个物品都有无穷多个。然后问从这些物品种挑选一些物品放背包里你所挑选东西的最大价值是多少 这道题限制条件有点多所以此时我们可能会有非常多的贪心策略。
比如只考虑体积这个限制条件往背包装的话肯定会选择体积最小的往背包里装因为装的多价值可能更大。那只考虑体积的贪心策略的最大价值是8 还有只考虑价值不是让价值最大吗那就疯狂装价值最大的但是因为背包容量的限制只能装一个价值为10的1号物品。然后去装价值为7的2号物品但是背包装不下所以接下来考虑价值为1的3号物品。在这种贪心策略下的最大价值是13 甚至还可以考虑单位体积价值因为2最大但是因为容量的限制只能装一个1号物品然后考虑1.75但是装不下然后就考虑3号物品你会发现这个策略和只考虑价值的策略是一样的。 虽然上面想了三种贪心策略但是细心发现这三种策略都错因为如果最大容量是8的话那装两个2号物品的最大价值是14比上面的都大。
虽然最后两个例子贪心并没有解决问题但是希望已经搞懂什么是贪心策略就是 贪婪 鼠目寸光说白了只考虑眼前的最优解并不考虑全局的最优解然后通过眼前的最优解“希望” 得到全局最优解。但是你会发现鼠目寸光并不一定能得到最后的结果。但是例子又是正确的为什么正确待会我们证明一下。
2.贪心算法的特点 1.贪心策略的提出 贪心策略的提出是没有标准以及模板的可能每一道题的贪心策略都是不同的 2.贪心策略的正确性 因为有可能 “贪心策略” 是一个错误的方法正确的贪心策略我们是需要 “证明的”。
想证明一个贪心策略是错的还是挺简单的举一个反例就行了。就比如例二 更短的路径和是7例三 选择两个2号物品价值是最大的。这样就把之前的贪心策略全部都给推翻了。所以想说一个贪心策略是错的还是挺简单的。但是例一 找零问题每次都去选可选的面额最大的就能用最少的张数凑成46块钱如何证明它是对的呢
不能说凭感觉此时看这样一个例子比如还是凑46但是现在你的面额是 [20、18、10、5、1]如果依旧按照贪心策略你会选择两张20元的、一张5元的、一张1元的。但是由于此时有18块钱我可以选两张18元的再选一个10元的才三张就能凑46元。然后你刚刚的贪心就不对了。所以不能说凭感觉一定要有严格的证明。
常用的证明方法数学中见过的所有证明方法。
证明找零问题 [20、10、5、1]
我们先不管策略以及最优解是什么我们先证明一个性质
假设最优解用了20块钱A张、10块钱B张、5块钱C张、1块钱D张此时我们先证明一个性质B、C、D是有取值范围的。
先考虑BB的取值范围有三种B 2 B 2B 2 为什么考虑2因为2张10可以凑成一张20。所以就把B分为222三种情况考虑。 我们很好证明前两种情况不是B的最优解如果想用10B用的数目超过2张那么任意两种10都可以用一张20替换那用20来代替10绝对是比刚刚用两种10块更优的。所以B绝对不可能超过2。 同理B2也是不可能存在的原因和上面一样如果B用了两种10块的那直接用一张20的替换不是更优的。 由此可以得到一个性质在最优解中B的张数绝对是小于2的或者可以说的小于等于1。在最优解中B最多就是一张要么没有。 同理C是和B一样的要么C 2、C 2、C 2最终在最优解中C的数目最多1张要么没有。 同理D因为5张D才可以凑出来一张CD还是分三种情况D 5、D 5、D 5, 同理前面两种是不存在的D超过5张不如用一张CD等于5张也是不如用一张C所以D 5 或者 D 小于等于 4 这是我们证明之前得到的性质10块钱不超过1张5块钱不超过1张1块钱不超过4张。
接下来我们证明方法就是等效法。 设贪心策略最后用的张数是 [a、b、c、d]最优解 [A、B、C、D]。 接下来我们只要证明出来 a Ab Bc Cd D。那我们就可以说我们贪心就是最优解。
先证明第一个a回忆一下我们的贪心[a、b、c、d]怎么来的我们的贪心策略是能用a就用a直到a不能用了在用b。所以用这个贪心策略可以得到 a A绝对不可能是 a A如果小了就不是贪心策略因为我们贪心策略就是能用20就尽量用20所以a A。
然后我们还可以证明 a 不可能大于 A如果 a A说明A比较小别忘了整个钱数是不变的如果A比较小那么少的20块钱就会让B、C、D去凑你会发现根本凑不出来注意刚才的性质10块钱不超过1张5块钱不超过1张1块钱不超过4张所能凑出来最大的钱是10 5 4 19根本凑不出20。如果 a 不能大于 A。
因此得到一个结论 a A 当 a A那 b c d 和 B C D 所凑的钱是一样的。 当凑的钱是一样的时候 我们可以得到 b B因为贪心我们会尽可能的选择10块钱此时 b B 同理我们也可以证明 b 不可能大于 B原因和之前的一样如果B小的话它会让C和D凑10块钱但是C和D凑不出来10块钱C最多一张5块钱D最多四张1块钱5 4 9 最多凑9块钱根本凑不出10块钱所以 b 不可能大于 B。
因此 b B 同理 c C 那 d 自然等于 D。 我们严格证明出来贪心策略和最优解是一致的因此贪心策略得到的结果绝对是最优解。
3.学习贪心的方向
遇到不会的贪心题很正常把心态放平。 前期学习的时候把重点放在贪心的策略上把这个策略当成经验吸收。往后遇到相同类型的题目时可以用经验去解决这道问题。 当知道贪心是正确的时候要想到如何去证明。
