亦往沧劫

Loading...

0%

贪心算法

发表于 更新于 分类于 Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

前言

先奉上一段千古名句：
模拟只会猜题意，贪心只能过样例。
数学上来先打表，DP一般看规律。
组合数学靠运气，计算几何瞎暴力。
图论一顿套模板，数论只会GCD。

基本概念

  所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
  贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
  所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

基本要素

一、贪心选择性质
  所谓贪心选择性质是指所求问题的总体最优解能够通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们仅仅考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
  对于一个详细问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的总体最优解。
二、最优子结构性质
  当一个问题的最优解包括其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

基本思路

1、建立数学模型来描述问题。
2、把求解的问题分成若干个子问题。
3、对每一子问题求解，得到子问题的局部最优解。
4、把子问题的解局部最优解合成原来解问题的一个解。

*贪心法正确性证明

  贪心法的正确性证明是个难点，尤其是在非常有限的竞赛时间内。所以，很多选手往往是大胆假设自己选择的贪心策略是正确的，这样难免会出错，但也是一种不得已而为之的办法。其实贪心法的证明虽然不容易，但一些常见的方法还是值得总结的。
  当一个贪心算法不能确定其100%正确，使用之前就应该尝试证明它的不正确性。而要证明其不正确，一种最简单的方法就是举一个反例。

举例

独木舟

题目链接：https://www.51nod.com/Challenge/Problem.html#!#problemId=1432

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long N,M;
	long long a[10020];
	cin>>N>>M;
	for(int i=0;i<N;i++)
		cin>>a[i];
	sort(a,a+N);
	long long l=0,r=N-1,ans=0;
	while(l<=r)
	{
		if(a[l]+a[r]<=M)
			l++;
		r--;
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}

聪明的木匠

题目链接：https://www.51nod.com/Challenge/Problem.html#!#problemId=1117

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N,t,res,ans=0;
	cin>>N;
	priority_queue<int,vector<int>,greater<int> >Q;
	for(int i=0;i<N;i++)
	{
		cin>>t;
		Q.push(t);
	}
	while(Q.size()>1)
	{
		res=Q.top();
		Q.pop();
		res+=Q.top();
		Q.pop();
		Q.push(res);
		ans+=res;
	}
	cout<<ans<<endl;
	return 0;
}

不重叠的线段

题目链接：https://www.51nod.com/Challenge/Problem.html#!#problemId=1133

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
struct demo{int l,r;}line[10020];
bool cmp(demo a,demo b){return a.r<b.r;}
int main()
{
	int N,ans=1;
	cin>>N;
	for(int i=0;i<N;i++)
		cin>>line[i].l>>line[i].r;
	sort(line,line+N,cmp);
	demo t=line[0];
	for(int i=1;i<N;i++)
	{
		if(t.r<=line[i].l)
		{
			ans++;
			t=line[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}

赏点呗！