深入理解贪心算法
上完了贪心这一讲，并且完成了课中的题目，你可能还是一头雾 水，你的感受是非常正常的，因为贪心算法并不像排序算法那样 有很强的模板性，掌握了几种排序的写法就可以应对所有的排序 问题。 上节课我总结贪心算法的时候，提到了一个重点：贪心算法解决 问题的正确性很多时候都是“显而易见”的，如果问题中存在“显而 易见”的逻辑，那么说不定就可以用贪心算法解决哦。 我准备用几个经典的题目来帮你加深理解贪心算法。
1.股票买卖问题
考虑下面的问题： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完 成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之 前的股票）。
示例 1: 输入: 6 7 1 5 3 6 4 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价 格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票 价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例2： 输入: 5 7 6 4 3 1 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0
2.货币找零问题
现在来看另一个经典问题：货币找零。 生活中，商家向顾客找零钱的时候往往优先找大面额的货币，这 样可以保证客户拿到的货币数量是最少的，方便顾客清点确认， 货币找零中的贪心思路同样是“显而易见”的，这种显而易见的特 性与货币的面额设计息息相关：低面额的货币大于等于两张才有 可能凑齐高面额的货币。你可以思考一下我们所使用的真实的货 币面额：1 2 5 10 50 100 是不是满足这个设定。 这就代表了每当 你使用一张高面额的货币时，总是优于使用多张小面额的货币 的。
3.背包问题
回到我们熟悉的背包问题中来，背包问题也是一个经典的贪心算 法VS动态规划的问题。随堂测题目中明确了物品可以切割，那么 这个题目就存在显而易见的逻辑：我们把物品按照单位体积价值 从高到低依次排序放入即可，如果最后一个物品不能整体放入， 那么把物品切割为背包剩余体积的大小放入即可。
股票买卖1解析
这个题中“显而易见”的逻辑在哪里呢？那就是把股票交易的时间 缩小到今天和明天，因为可以无限次买卖，所以只要今天的股票 价格比明天低，我们就可以在今天买入，在明天卖出。也就是说 根据每天的股票价格都可以立即作出是否购买的决定。 下面是这个题目的贪心解法：
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int p[n+1];
//因为后面贪心时从下标2开始查找，所以这里要做好保护
if(n < 2){
cout<<0;
return 0;
}
for(int i =1;i<= n;i++)
cin>>p[i];
int sum = 0;
int t = 1;
for(int i = 2;i<=n;i++)
{
//显而易见：只要第二天比前一天价格高，就可以买卖
if (p[i] > p[i-1])
sum += p[i] - p[i-1];
}
cout<<sum;
return 0;
}
股票买卖2解析
同样的题目，如果将买卖的次数限制为只能买卖一次的话，你会 发现上面的解法不能用了。同样的输入数据在只能买卖一次的情 况下，计算收益的方式完全不同，仍以示例1为例： 输入: 6 7 1 5 3 6 4 输出: 5 解释: 因为只能买卖一次，所以一定要挑合适的买点，在第 2 天 （股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候 卖出, 这笔交易所能获得利润 = 6-1 = 5 。 重新分析问题，在只能买卖一次的情况下如何计算出最高收益 呢？ 不同于背包问题，股票买卖这个题目中股票价格这组数据，有明 确的先后关系，所以你不能对原始数据进行排序。你也不能找到 最大值和最小值进行相减，因为最大值可能出现在最小值之前。 拿到某一天的价格，我们并不能做出买卖的决定，你需要得对所 有数据做出分析之后，才能知道在哪天进行买卖。在这种情景 中，枚举所有的情况肯定是可行的，但是运算比较复杂，这里我 展示动态规划的写法，代码比较简单也易于理解。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int p[n+1];
//数据保护
if(n < 2){
cout<<0;
return 0;
}
for(int i =1;i<=n;i++)
cin>>p[i];
//minp保存当前日期之前出现的最低价格
//maxs 代表当前收益的最大值
int minp = INT_MAX,maxs = 0;
for(int i = 1 ; i <= n; i++){
if(p[i] < minp)
//当前的价格比之前的最低价格还低
//那就不用算了，直接更新最低价格
minp = p[i];
else if(p[i] - minp > maxs)
//如果当前价格比之前的最低价格低，证明可以买卖
//计算一下此时卖出的收益，如果比之前的收益更高，
那么更新收益
maxs = p[i] - minp;
}
cout<<maxs;
return 0;
}
2.货币找零问题
现在来看另一个经典问题：货币找零。 生活中，商家向顾客找零钱的时候往往优先找大面额的货币，这 样可以保证客户拿到的货币数量是最少的，方便顾客清点确认， 货币找零中的贪心思路同样是“显而易见”的，这种显而易见的特 性与货币的面额设计息息相关：低面额的货币大于等于两张才有 可能凑齐高面额的货币。你可以思考一下我们所使用的真实的货 币面额：1 2 5 10 50 100 是不是满足这个设定。 这就代表了每当 你使用一张高面额的货币时，总是优于使用多张小面额的货币 的。 下面是解决找零问题的代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
//p中保存着真实的面额
int p[7] = {100,50,20,10,5,2,1};
//sump代表找零金额，cnt代表最终的找零钞票张数
int sump,cnt;
cin>>sump;
for(int i =0;i<7;i++) {
cnt += sump/p[i];
sump = sump%p[i];
if(sump == 0)
break;
}
cout<<cnt;
return 0;
}
如果一个题目打破了真实的货币规则，可以自定义货币面额的 话，贪心算法就不能用了，比如货币面额为 100 99 1。这并不是 一个规范的货币面额组合，2 * 99 > 100，那么这种货币组合中， 当 找零金额为 198时，使用贪心算法计算得到的张数是 1张 100 元+ 98张 1元 = 99张，而真实的最小面额为 99元 * 2。这个时候 又得使用动态规划了。由于这个题目的动态规划解法比较复杂， 所以我就暂时不展示了。
3.背包问题
回到我们熟悉的背包问题中来，背包问题也是一个经典的贪心算 法VS动态规划的问题。随堂测题目中明确了物品可以切割，那么 这个题目就存在显而易见的逻辑：我们把物品按照单位体积价值 从高到低依次排序放入即可，如果最后一个物品不能整体放入， 那么把物品切割为背包剩余体积的大小放入即可。 下面是一份示例代码，使用的都是最朴素的写法：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int c,n;
cin>>c>>n;
double w[10000],v[10000],p[10000];
for(int i =1;i<=n;i++) {
//输入第 i 个物品的体积和价值
cin>>v[i]>>w[i];
p[i] = w[i] / v[i];
}
//冒泡排序
for(int i = n - 1;i >= 1;i--) {
for(int j = 1;j <= i;j++) {
// j 代表物品的编号，按照p从高到低排列
if(p[j] < p[j+1]) {
//swap可以快速实现交换,要交换 p w v 都要交
换，
//这样才能下标对齐
swap(p[j],p[j+1]);
swap(v[j],v[j+1]);
swap(w[j],w[j+1]);
}
}
}
double cnt = 0;
for(int i =1;i<=n;i++) {
//证明可以放得下
if (c - v[i] > 0) {
c -= v[i];//扣除体积
cnt += w[i];//增加价值
} else {
// else 代表放不下说明这是最后一个可以放入的物品
了
cnt += c*p[i];
break;
}
}
cout<<fixed<<setprecision(2)<<cnt;
}
我们还没有接触到结构体，w v p 是相同数据类型的，所以可以 合并成一个二维数组化简代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int c,n;
cin>>c>>n;
//二维数组的第二维分别代表体积、价值和价值体积比
double wp[10000][3];
for(int i =1;i<=n;i++) {
//输入第 i 个物品的体积和价值,同时计算出比值
cin>>wp[i][0]>>wp[i][1];
wp[i][2] = wp[i][1] / wp[i][0];
}
//冒泡排序
for(int i = n - 1;i >= 1;i--) {
for(int j = 1;j <= i;j++) {
// j 代表物品的编号，按照从高到低排列
if(wp[j][2] < wp[j+1][2]) {
//swap可以快速实现交换
swap(wp[j],wp[j+1]);
}
}
}
double cnt = 0;
for(int i =1;i<=n;i++) {
//证明可以放得下
if (c - wp[i][0] > 0) {
c -= wp[i][0];//扣除体积
cnt += wp[i][1];//增加价值
} else {
// else 代表放不下说明这是最后一个可以放入的物品
了
cnt += c*wp[i][2];
break;
}
}
cout<<fixed<<setprecision(2)<<cnt;
}
如果我修改题目的条件为“物品不可切割”，那么贪心算法就失效 了，有点类似于货币找零的问题，想象一下以下这组数据。 背包体积：100 物品体积 和 价值： 70 90 40 40 60 60 虽然物品 1 的单位体积价值最高，但是放入物品1后剩下的就放不 进去了，最终背包中的价值只有 90.如果我们放入物品 2 和物品 3，就能获得价值 100。这种不可切割同时每个物品只有一个的背 包问题是“01背包问题”，同样需要使用动态规划来解决。 希望通过本篇文章，能帮你加深贪心算法的理解。我们可以建立 这样一个概念：如果不能用贪心算法解决，那么就尝试用动态规 划去解决。 后面我们学习了动态规划，你就可以一展身手啦~
三国游戏