欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

思维暴力的贪心

程序员文章站 2022-09-21 09:09:44
贪心比赛时,题目都会有时间限制和内存限制。面对它们,我们要思考各种算法的运行次数以及时间复杂度。这时,出现了一个头脑简单的家伙------贪心。定义:严格讲,贪心只是一种策略或方法,而不是算法,推进的每一步不是依据某一固定的递推式,而是做一个当时看似最佳的贪心选择,不断地将问题实例归纳为更小的相似子问题。归纳、分析、选择正确合适的贪心策略,是正确解决贪心问题的关键。优势:贪心法的优势在于编程简单、运行效率高、空间复杂度低等。贪心例题反例:1.数塔问题:如图所示为一个数字三角形,请编程计算...

贪心

比赛时,题目都会有时间限制和内存限制。面对它们,我们要思考各种算法的运行次数以及时间复杂度。

这时,出现了一个头脑简单的家伙------贪心

定义:

严格讲,贪心只是一种策略方法,而不是算法,推进的每一步不是依据某一固定的递推式,而是做一个当时看似最佳的贪心选择,不断地将问题实例归纳为更小的相似子问题。归纳分析选择正确合适的贪心策略,是正确解决贪心问题的关键。

优势:

贪心法的优势在于编程简单运行效率高空间复杂度低等。

贪心例题

反例:

1.数塔问题:

如图所示为一个数字三角形,请编程计算从顶到底的某处的一条路径,使该路径经过的数字总和最大,只要求输出总和。
1、一步可沿左斜线向下或右斜线向下走;
2、三角形行数小于等于100;
3、三角形中的数字为0,1,2,…99;
测试数据通过键盘逐行输入如下:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

此题就不可用贪心法。

正解需要用递推

话不多说,我们直接进例题。

例题

例一:

有一天,阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时,远处突然出现一股烟尘, 弥漫着直向上空飞扬,朝他这儿卷过来,而且越来越近。靠近以后,他才看清原来是一支马队,他们共有四十人,一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋,从丛林中一直来到那个大石头跟前,喃喃地说道:“芝麻,开门吧!”随着那个头目的喊声,大 石头前突然出现一道宽阔的门路,于是强盗们鱼贯而入。阿里巴巴待在树上观察他们,直到 他们走得无影无踪之后,才从树上下来。他大声喊道: “芝麻,开门吧!”他的喊声刚落,洞门立刻打开了。 他小心翼翼地走了进去一下子惊呆了,洞中堆满了 财物,还有多得无法计数的金银珠宝,有的散堆在地 上,有的盛在皮袋中。突然看见这么多的金银财富, 阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所 积累起来的宝窟。为了让乡亲们开开眼界,见识一下 这些宝物,他想一种宝物只拿一个,如果太重就用锤子凿
开,但毛驴的运载能力是有限的,怎么才能用驴 子运走最大价值的财宝分给穷人呢? 阿里巴巴陷入沉思中……

Input

一个整数n,表示宝物的个数;一个整数m,表示毛驴的载重量。
接着输入n行,每行输入每个宝物的重量w和价值v。

Output

带走宝物的数量。

自信 分析一波

需要比较每个宝物的性价比,再按性价比从高到低拉走真的太暴力了

题解

#include<bits/stdc++.h>
using namespace std;
struct three
{
	float w;
	float v;
	float p;
}a[1010];
bool mycmp(three a,three b)
{
	return a.p>b.p;
}
int main()
{
	int n;
	float sum=0,m;//弱弱的提醒一句,sum和m一定要定义为浮点型!!!要不然就没有输出哦。
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>a[i].w>>a[i].v;
		a[i].p=a[i].v/a[i].w;
	}
	sort(a,a+n,mycmp);
	for(int i=0;i<n;i++)
	{
		if(m>a[i].w)
		{
			m-=a[i].w;
			sum+=a[i].v;
		}
		else
		{
			sum+=m*a[i].p;
			break;
		}
	}
	cout<<fixed<<setprecision(2)<<sum;
	return 0;
}

例二:

元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了
保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。

Input

第一行包括一个整数w,为每组纪念品价格之和的上限;第二行为一个整数n,表示购来纪念品的总件数。
第3到n+2行每行包含一个正整数pi(5<=pi<=w),表示所应对纪念品的价格。

Output

一个整数,表示最少的分组数目。

数据范围

50%的数据满足:1<=n。
100%的数据满足:1<=n<=30000,80<=w<=200。

题解

#include<bits/stdc++.h>
using namespace std;
int main()
{
	cin>>w>>n;
	for(int i=1;i<=n;i++)
      		cin>>a[i];
	sort(a+1,a+n+1);
	int i=1,j=n,m=0;
	for(;i<=j;m++)
	{
       		if(a[i]+a[j]<=w)
         	{
 		i++;  
 		j--;
           	}
       		else 
       			j--;
	}
	cout<<m<<endl;
	return 0;
}

这…是不是有点过与简洁?(内心绽放花朵

In the end

贪心算法是从问题的初始状态出发,通过若干次的贪心选择而得到的最优值(或者较优值) 的一种求解问题的策略,即贪心策略

换句话说,贪心策略是一种每次在决策时采取当前意义下最优策略的算法,做出的选择只是在某种约束条件下的局部最优解****或较优解,并不一定是全局的最优解或较优解。不过,某些特定的问题是可以利用贪心算法求得其最优解或较优解的。

欢迎在评论区讨论

本新手对dalao
Orz Orz Orz

本文地址:https://blog.csdn.net/zhengbowen_zbw/article/details/107616774

相关标签: 贪心算法 c++