程序员算法基础——贪心算法
yangjingdong00 2018-06-04
前言
贪心是人类自带的能力，贪心算法是在贪心决策上进行统筹规划的统称。
比如一道常见的算法笔试题----跳一跳：
- 有n个盒子排成一行，每个盒子上面有一个数字a[i]，表示最多能向右跳a[i]个盒子;
- 小明站在左边第一个盒子，请问能否到达最右边的盒子?
- 比如说：[1, 2, 3, 0, 4] 可以到达第5个盒子;
- [3, 2, 1, 0, 4] 无法到达第5个盒子;
我们自然而然能产生一种解法：尽可能的往右跳，看最后是否能到达。
本文即是对这种贪心决策的介绍。
正文
贪心算法基础概念
狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解;这种贪心算法是动态规划的一种特例。能用贪心解决的问题，也可以用动态规划解决。
而广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。以跳一跳的题目为例：
- 我们发现的题目的核心在于向右能到达的最远距离，我们用maxRight来表示;
此时有一种贪心的策略：从第1个盒子开始向右遍历，对于每个经过的盒子，不断更新maxRight的值。
贪心算法的思考过程
贪心的思考过程类似动态规划，依旧是两步：大事化小，小事化了。
大事化小：
一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题;
小事化了：
从小问题找到决策的核心，确定一种得到最优解的策略，比如跳一跳中的向右能到达的最远距离;
在证明局部的最优解是否可以推出全局最优解的时候，常会用到数学的证明方式。
贪心算法的具体应用
1、纸币找零问题
有1元、2元、5元、10元的纸币分别有a[1], a[2], a[3], a[4]张，要用这些纸币凑出m元，至少要用多少张纸币?
如果是动态规划：
- 要凑出m元，必须先凑出m-1、m-2、m-5、m-10元，我们用dp[i]表示凑出i元的最少纸币数;
- 有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1;
- 容易知道dp[1]=dp[2]=dp[5]=dp[10]=1;
根据以上递推方程和初始化信息，可以容易推出dp[1~m]的所有值。
似乎有些不对?平时我们找零钱有这么复杂吗?
从贪心算法角度出发，当m>10且我们有10元纸币，我们优先使用10元纸币，然后再是5元、2元、1元纸币。
- 从日常生活的经验知道，这么做是正确的，但是为什么?
- 假如我们把题目变成这样，原来的策略还能生效吗?
- 有1元、5元、7元的纸币分别有a[1], a[2], a[3]张，要用这些纸币凑出m元，至少要用多少张纸币?
接下来我们来分析这种策略：
- 已知对于m元纸币，1，2，5元纸币使用了a，b，c张，我们有a+2b+5c=m;
假设存在一种情况，1、2、5元纸币使用数是x，y，z张，使用了更少的5元纸币(z
我们令k=5*(c-z)，k元纸币需要floor(k/2)张2元纸币，k%2张1元纸币;(因为如果有2张1元纸币，可以使用1张2元纸币来替代，故而1元纸币只能是0张或者1张)
容易知道，减少(c-z)张5元纸币，需要增加floor(5*(c-z)/2)张2元纸币和(5*(c-z))%2张纸币，而这使得x+y+z必然大于a+b+c。
由此我们知道不可能存在使用更少5元纸币的更优解。
所以优先使用大额纸币是一种正确的贪心选择。
对于1、5、7元纸币，比如说要凑出10元，如果优先使用7元纸币，则张数是4;(1+1+1+7)
但如果只使用5元纸币，则张数是2;(5+5)
在这种情况下，优先使用大额纸币是不正确的贪心选择。(但用动态规划仍能得到最优解)
2、服务器任务安排问题
服务器有n个任务要执行，每个任务有开始时间Si秒和结束时间Ti秒，同一时间只能执行一个任务。
问如何安排任务，使得在时间m内尽可能多的完成任务。
如果是动态规划：
前i秒的完成的任务数，可以由前面1~i-1秒的任务完成数推过来。
- 我们用dp[i]表示前i秒能完成的任务数;
在计算前i秒能完成的任务数时，对于第j个任务，我们有两种决策：
- 不执行这个任务，那么dp[i]没有变化;
- 执行这个任务，那么必须腾出来(Sj, Tj)这段时间，那么dp[i] = max(dp[i], dp[ S[j] ] ) + 1;
比如说对于任务j如果是第5秒开始第10秒结束，如果i>=10，那么有dp[i]=max(dp[i], dp[5] + 1);(相当于把第5秒到第i秒的时间分配给任务j)
再考虑贪心的策略，现实生活中人们是如何安排这种多任务的事情?我换一种描述方式：
- 小明在学校兼职，小明一天兼职的时间有10个小时;
- 现在有多个兼职岗位，每个岗位有个开始时间和结束时间，小明同一时间只能做一个兼职;
问小明每天最多能做几份兼职?
我们自然而然会想到一个策略：先把结束时间早的兼职给做了!
为什么?
因为先做完这个结束时间早的，能留出更多的时间做其他兼职。
我们天生具备了这种优化决策的能力。
3、分糖果问题
n个小朋友玩完游戏后，老师准备给他们发糖果;
每个人有一个分数a[i]，如果比左右的人分数高，那么糖果也要比左右的多，并且每个小朋友至少有一颗。
问老师最少准备多少糖果。
这是一道LeetCode题目。
这个题目不能直接用动态规划去解，比如用dp[i]表示前i个人需要的最少糖果数。
因为(前i个人的最少糖果数)这种状态表示会收到第i+1个人的影响，如果a[i]>a[i+1]，那么第i个人应该比第i+1个人多。
即是这种状态表示不具备无后效性。
如果是我们分配糖果，我们应该怎么分配?
答案是：从分数最低的开始。
按照分数排序，从最低开始分，每次判断是否比左右的分数高。
假设每个人分c[i]个糖果，那么对于第i个人有c[i]=max(c[i-1],c[c+1])+1; (c[i]默认为0，如果在计算i的时候,c[i-1]为0，表示i-1的分数比i高)
但是，这样解决的时间复杂度为O(NLogN)，主要瓶颈是在排序。
如果提交，会得到Time Limit Exceeded的提示。
我们需要对贪心的策略进行优化：
- 我们把左右两种情况分开看。
如果只考虑比左边的人分数高时，容易得到策略：
- 从左到右遍历，如果a[i]>a[i-1]，则有c[i]=c[i-1]+1;否则c[i]=1。
再考虑比右边的人分数高时，此时我们要从数组的最右边，向左开始遍历：
- 如果a[i]>a[i+1], 则有c[i]=c[i+1]+1;否则c[i]不变;
这样讲过两次遍历，我们可以得到一个分配方案，并且时间复杂度是O(N)。
4、小船过河问题
n个人要过河，但是只有一艘船;船每次只能做两个人，每个人有一个单独坐船的过河时间a[i]，如果两个人(x和y)一起坐船，那过河时间为a[x]和a[y]的较大值。
问最短需要多少时间，才能把所有人送过河。
题目给出关键信息：1、两个人过河，耗时为较长的时间;
还有隐藏的信息：2、两个人过河后，需要有一个人把船开回去;
要保证总时间尽可能小，这里有两个关键原则：应该使得两个人时间差尽可能小(减少浪费)，同时船回去的时间也尽可能小(减少等待)。
先不考虑空船回来的情况，如果有无限多的船，那么应该怎么分配?
答案：每次从剩下的人选择耗时最长的人，再选择与他耗时最接近的人。
再考虑只有一条船的情况，假设有A/B/C三个人，并且耗时A
那么最快的方案是：A+B去, A回;A+C去;总耗时是A+B+C。(因为A是最快的，让其他人来回时间只会更长，减少等待的原则)
如果有A/B/C/D四个人，且耗时A
- 最快的来回送人方式，A+B去;A回;A+C去，A回;A+D去; 总耗时是B+C+D+2A (减少等待原则)
- 最快和次快一起送人方式，A+B先去，A回;C+D去，B回;A+B去;总耗时是 3B+D+A (减少浪费原则)
对比方案1、2的选择，我们发现差别仅在A+C和2B;
为何方案1、2差别里没有D?
因为D最终一定要过河，且耗时一定为D。
如果有A/B/C/D/E 5个人，且耗时A
仍是从最慢的E看。(参考我们无限多船的情况)
- 方案1，减少等待;先送E过去，然后接着考虑四个人的情况;
- 方案2，减少浪费;先送E/D过去，然后接着考虑A/B/C三个人的情况;(4人的时候的方案2)
到5个人的时候，我们已经明显发了一个特点：问题是重复，且可以由子问题去解决。
根据5个人的情况，我们可以推出状态转移方程dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根据我们考虑的1、2、3、4个人的情况，我们分别可以算出dp[i]的初始化值：
dp[1] = a[1]; dp[2] = a[2]; dp[3] = a[2]+a[1]+a[3]; dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);
由上述的状态转移方程和初始化值，我们可以推出dp[n]的值。
这是一道贪心和动态规划的结合题目，动态规划的决策过程中用到了贪心的策略。
总结
贪心的学习过程，就是对自己的思考进行优化。
