贪心算法
贪心算法(Greedy Algorithm)是一种
(1)在每一步选择中都采取在当前状态下的最优决策(局部最优)
(2)并希望由此导致的最终结果也是全局最优的算法
贪心算法与一般的搜索，以及后面要讲的动态规划相比，不同之处在于:它不对整个状态空间进行遍历或计算，而是始终按照局部最优选择执行下去，不再回头。
因为这个特性，贪心算法不一定能得到正确的结果
除非可以证明，按照适当的方法做出局部最优选择,依然可以得到全局最优结果
能用贪心求解的题目，也都可以用搜索或动态规划求解，但贪心一般是最高效的
引入:零钱兑换问题
322.零钱兑换
https://leetcode.cn/problems/coin-change/
class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount+1,INT_MAX-1); dp[0]=0; for(int i=1;i<=amount;i++) { for(int j=0;j<coins.size();j++) { if(coins[j]<=i) { dp[i]=min(dp[i-coins[j]]+1,dp[i]); } } } dp[amount]=dp[amount]==INT_MAX-1?-1:dp[amount]; return dp[amount]; } };
给一个硬币面额的可选集合coins,求拼成金额amount最少需要多少枚硬币。
例: coins = [20, 10, 5, 1], amount=46
答案: 46=20+20+5+ 1
零钱兑换:贪心
根据我们平时找钱的思路，一般我们会先考虑面值大的，零钱再用面值小的凑齐
“每次都选尽量大的面值”就是一个贪心思想
零钱兑换:贪心法的反例
零钱兑换:搜索
贪心算法的证明
由“零钱兑换"问题可以看出，贪心算法实际上是在状态空间中按局部最优策略找了一条路径。
贪心算法不一定能得出正确的解， 在大部分题目上不能随便使用。
遇到题目，一般先想搜索、动态规划等基于全局的解法，若时间复杂度太高,再考虑贪心。
若要使用贪心算法，必须先证明其正确性。
除了反证法、数学归纳法等大家熟悉的方法外,我们再介绍几种常用的手法。
实战
860.柠檬水找零
https://leetcode.cn/problems/lemonade-change/description/
class Solution { public: bool lemonadeChange(vector<int>& bills) { coins[5] = coins[10] = coins[20] = 0; for(int bill : bills) { coins[bill]++; if(!exchange(bill - 5)) return false; } return true; } private: bool exchange(int amount) { for(int x : {20, 10, 5}) { while (amount >= x && coins[x] > 0) { amount -= x; coins[x]--; } } return amount == 0; } unordered_map<int, int> coins; };
“零钱兑换"类问题在面值互相构成倍数时，贪心算法成立
在本题中，面值为[5, 10, 20]
如果能用1个10块找零,那用2个5块必然也也可以
也就是说，做出“用10块找零”这个决策,未来的可能性包含了” 用2个5块找零”以后未来的可
能性一决策包容性
所以本题可以贪心:优先使用面值较大的找零
455.分发饼干
https://leetcode.cn/problems/assign-cookies/description/
class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(),g.end()); sort(s.begin(),s.end()); int candy=0,child=0; while(child<g.size() && candy<s.size()) { if(g[child]<=s[candy]) { child++; } candy++; } return child; } };
两种思路
一块饼干(尺寸s[j]) 发给谁?发给满足g[i] <= s[j]的最大g[i] (刚刚好能满足的孩子)
一个孩子(胃口g[i])吃哪块饼干?吃满足s[j] >= g[i]的最小s[j],不存在就别吃了
通俗点讲就是小饼干给小孩子，大饼干给大孩子,不能满足就不给了
决策包容性: -块饼干总是想要满足一一个孩子的,满足胃口更大的孩子,未来的可能性包含了满足
胃口更小孩子的可能性
把饼干和孩子排序,代码更容易实现
贪心算法的证明
决策范围扩展
在思考贪心算法时,有时候不容易直接证明局部最优决策的正确性
此时可以往后多扩展一一步, 有助于对当前的决策进行验证
实战
122.买卖股票的最佳时机II
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
class Solution { public: int maxProfit(vector<int>& prices) { int ans = 0; for(int i = 1; i < prices.size(); i++){ ans += max(prices[i] - prices[i - 1], 0); } return ans; } };
这是一个预言家的炒股状态一知道未来每 天的价格
当前持有股票，卖不卖?往后看一天，明天还涨那肯定不卖,明天跌那肯定卖啊!
当前没有股票，买不买?往后看一天,明天涨那肯定买,明天跌那肯定先不买!
最后就是完美结果一获得所有 prices[i]- prices[i- 1]> 0区间的收益
45.跳跃游戏II
https://leetcode.cn/problems/jump-game-ii/
class Solution { public: int jump(vector<int>& nums) { int now = 0; int ans = 0; while (now < nums.size() - 1) { int right = now + nums[now]; if (right >= nums.size() - 1) return ans + 1; int nextRight = right; int next = now; for(int i = now + 1; i <= right; i++) { if(i + nums[i] > nextRight) { nextRight = i + nums[i]; next = i; } } now = next; ans++; } return ans; } };
看一下往后跳两步的所有可能性
贪心策略:若a能到b1, b2,b3,而b1, b2, b3能到的最远位置分别为C1, c2, c3,那应该从a
跳到c1, c2 ,c3中最大的一个对应的b。
Leetcode示意图
决策包容性:同样都是跳1步,从a跳到“能跳得更远”的b,未来的可达集合包含了跳到其他
b的可达集合，所以这个局部最优决策是正确的。
邻项交换
经常用于以某种顺序“排序”为贪心策略的证明
证明在任意局面下，任何局部的逆序改变都会造成整体结果变差
实战
1665.完成所有任务的最少初始能量
https://leetcode.cn/problems/minimum-initial-energy-to-finish-tasks/
class Solution { public: int minimumEffort(vector<vector<int>>& tasks) { sort(tasks.begin(), tasks.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] - a[1] < b[0] - b[1]; }); int ans = 0; for(int i = tasks.size() - 1; i >= 0; i--) { ans = max(tasks[i][1], ans + tasks[i][0]); } return ans; } };
考虑任意一种做任务的顺序, 设做完第i+2到n个任务所需的初始能量最少为S
对于两个相邻任务:设第i个和第i+1个完成的任务分别是p和q
先做p,所需初始能量为: max(max(minimum[q], S+actual[q])+actual[p], minimum[p])
先做q,所需初始能量为: max(max(minimum[p], S+actual[p])+actual[q], minimum[q])
若先做p比较优,则应满足(拆括号,消去一样的项)
max(minimum[q] + actual[p], minimum[p]) < max(minimum[p] + actual[q], minimum[q)
因为必定有minimum[q] + actual[p] > minimum[q]
所以上式等价于minimum[q] + actual[lp] < minimum[p] + actuallq]
即actual[p] - minimum[p] < actual[lq] - minimum[q]
贪心策略:按照actual - minimum升序排序，以此顺序完成任务
(https://ke.qq.com/course/417774?flowToken=1041943)
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
