贪心算法

浅谈贪心算法

简单的说一下贪心算法及其运用

一.基本概念

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部的最优解。

举个例子来说就好比一条路上有两条路,一条路表面轻松,一条路表面艰难,但背后的路却谁也不知道,但这个算法永远都会选择那条轻松的路,而不管后面是怎么走的,简而言之目光短浅。但是目光短浅有的时候也可以求的最优解,这就要看问题本身了。

那么贪心算法在什么时候能够适用呢?

选择贪心算法的问题需要具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

在选择贪心算法的时候一定需要注意此性质,对于如何处理有后效性的题目,我们以后再做处理。

二.基本思路

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

三.适用问题

贪心算法只适用于从局部最优策略可以产生全局最优策略的题目,当然对于不满足的也可以使用,但不一定能适用!

对于贪心思路的正确性,一般来说都是不好去证明的,很多时候是靠自己感觉而来的。但是贪心思路的反例却比比较好找,找出反例便可以证明其错误性。


相信在阅读完上文的你应该大致了解了一下贪心算法把,接下来来看一道简单的例题,练练手吧!

四.例题

排队接水

有 n 个人在一个水龙头前排队接水,假如每个人接水的时间为 Ti​,请编程找出这 n 个人排队的一种顺序,使得 n 个人的平均等待时间最小。

这是一道非常简单的贪心题,很容易我们就可以知道,因为排队时,越靠近前面的时间计算的次数越多,因此越小的排在前面计算出来的结果就是最小的,所以这道题可以用贪心来进行解决。

(1)将时间从大到小进行排序

(2)将排序后的时间按顺序一次放入每个水龙头的队列中

(3)统计,输出答案

参考代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	int t;
	int num;
}a[1010];
int n;
double ans,sum;
bool cmp(node a,node b){
	return a.t<b.t;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].t);
		a[i].num=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){
		printf("%d ",a[i].num);
		sum+=(n-i)*a[i].t;
	}
	printf("\n");
	ans=sum/n;
	printf("%0.2lf",ans);
	return 0;
} 

另外放上几道练习题,有问题的可以评论或者QQ找我

P1031 均分纸牌 https://www.luogu.com.cn/problem/P1031

P1106 删数问题 https://www.luogu.com.cn/problem/P1106

P1020 导弹拦截 https://www.luogu.com.cn/problem/P1020


贪心比较重要的一点就是要多多练习,掌握一些基本的套路。

遇到问题如果不确定是否使用贪心算法,也可以大胆猜测,然后进行验证。

发表评论