贪心算法是指，在对问题求解中，对问题的每一步决策都采取当前意义下最优策略的算法，即问题的整体最优性可以由局部最优性来导出。
贪心算法的正确性需要证明，常见的手段有：微扰(邻项交换)，反证法，数学归纳法，范围缩放，决策包容性
我们来看几道基础的贪心题：
1.Acwing913排队打水 、 洛谷P1223排队接水
（两题题意一致，仅输入输出要求不同）
有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
输入格式
第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。
输出格式
输出一个整数，表示最小的等待时间之和。
数据范围
根据我们的日常经验，肯定是让打水时间越长的人越往后排，这样所有人的等待时间之和肯定最小，可是为什么这样是正确的？
证明：
贪心策略：按照每个人的打水时间长短对队伍进行排序，打水所需时间越少的越往前排。
易知，所有人的等待时间之和是：Sum = T1 * (n-1) + T2 * (n-2) + ... + T(n-1) * 1(n个人排队打水的情况下)
反证法，假设在最优情况下(即没有按照贪心的策略来安排打水），有Ti>Ti+1，那么我们将这两项交换:
交换前：Sum1 = T1 * (n-1) + T2 * (n-2) + ... +Ti * (n-i) + Ti+1 * (n-i-1) +...+ T(n-1) * 1
交换后：Sum2 = T1 * (n-1) + T2 * (n-2) + ... +Ti+1 * (n-i) + Ti * (n-i-1) +...+ T(n-1) * 1
Sum1 - Sum2 = Ti - Ti+1 > 0
交换这两项后结果更优，所以这不是最优策略，即贪心策略正确
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
using LL = long long; //本题会爆int，所以使用long long
const int N = 1e5+100;
int n;
int a[N];
int main()
{
scanf("%d",&n);
for(int i = 1; i<=n; i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
LL ans = 0;
for(int i = 1; i<=n; i++) ans += a[i] *(n-i);
printf("%lld\n",ans);
return 0;
}
再来介绍一个和本题类似的贪心题。
2.Acwing125.耍杂技的牛
农民约翰的N头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。奶牛们不是非常有创意，只提出了一个杂技表演：叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数N，表示奶牛数量。
接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第i行表示第i头牛的重量Wi以及它的强壮程度Si。
输出格式
输出一个整数，表示最大风险值的最小可能值。
数据范围
这题的贪心策略是将牛按重量+强壮程度为标准进行排序，越小的占据越高的位置，这样可以得到答案
证明：
我们用A来表示使用贪心策略得到的答案，用B来表示最优解的答案
①. A >= B,这很容易得出,所有解决此问题的策略得到的答案一定>=最优答案
②. A <= B
反证法，如果B不是由贪心策略得到的，那么存在Wi + Si > W(i+1) + S(i+1) ,( i 表示奶牛占据的位置，i 处于高位)，按照上一题的做法，我们对第i个位置和第i+1个位置上的奶牛进行交换，并分析前后的风险值得对比
交换前:
第 i 个位置上的奶牛： W1 + W2 + ... + W(i-1) - Si
第 i+1个位置上的奶牛： W1 + W2 + ... + Wi - S(i+1)
交换后
第 i 个位置上的奶牛： W1 + W2 + ... + W(i-1) - S(i+1)
第 i+1个位置上的奶牛： W1 + W2 + ... + W(i+1) - Si
分别减去共同的部分，得到：
交换前:
第 i 个位置上的奶牛： - Si
第 i+1个位置上的奶牛： Wi - S(i+1)
交换后
第 i 个位置上的奶牛： - S(i+1)
第 i+1个位置上的奶牛： W(i+1) - Si
再分别加上Si + S(i+1):
交换前:
第 i 个位置上的奶牛： S(i+1)
第 i+1个位置上的奶牛： Wi + Si
交换后
第 i 个位置上的奶牛： Si
第 i+1个位置上的奶牛： W(i+1) + S(i+1)
对第i+1个位置上的奶牛来说，交换过后，它的风险值减小了，所以A<=B得证
综合①②，我们得出A=B，即贪心策略就是最优策略
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
using PII = pair<int,int>;
const int N = 5e5+100;
int n;
PII c[N];
int main()
{
cin>>n;
for(int i = 0; i<n; i++)
{
int w,s;
cin>>w>>s;
c[i] = {w+s,w};
}
sort(c,c+n);
int ans = -1e9, up = 0;
for(int i = 0; i<n; i++)
{
int w = c[i].second, s = c[i].first-w;
ans = max(ans,up-s);
up += w;
}
cout<<ans<<endl;
return 0;
}
网友评论