思维暴力的贪心
贪心
比赛时,题目都会有时间限制和内存限制。面对它们,我们要思考各种算法的运行次数以及时间复杂度。
这时,出现了一个头脑简单的家伙------贪心。
定义:
严格讲,贪心只是一种策略或方法,而不是算法,推进的每一步不是依据某一固定的递推式,而是做一个当时看似最佳的贪心选择,不断地将问题实例归纳为更小的相似子问题。归纳、分析、选择正确合适的贪心策略,是正确解决贪心问题的关键。
优势:
贪心法的优势在于编程简单、运行效率高、空间复杂度低等。
贪心例题
反例:
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
上一篇: LibGdx学习过程(二)项目结构解析
下一篇: Python基础语法之条件控制语句