ACM第二周学习总结-贪心算法
这周学习了贪心算法。
贪心算法是按照某种最优策略将整个问题分解成一个个子问题,寻找最优解的方法。贪心算法对问题求解时,总是做出当前情况下最好的选择,它不是从整体上最优考虑,故贪心算法是局部最优解,不是整体最优解。
例题
1:
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
题意老鼠M磅的猫粮,用猫粮换取爪哇豆仓库里的爪哇豆。仓库有N个房间。第i个房间有J[i]磅的爪哇豆,需要F[i]磅的猫粮。老鼠不需要用房间里所有的爪哇豆来交换,如果他支付F[i]*a%磅的猫粮,他可以得到J[i]*a%磅的爪哇豆,求老鼠能获得爪哇豆的的最大数量(得出的结果为实数)。
代码
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int m,n;
struct House{
double j;
double f;
double rate;
};
double cmp(House a,House b){
return a.rate>b.rate;
}
int main()
{ int i;
double s;
House house[1002];
while(cin>>m>>n){
s=0;
if(m==-1&&n==-1)
break;
for(i=0;i<n;i++){
cin>>house[i].j>>house[i].f;
house[i].rate=house[i].j/house[i].f;
}
sort(house,house+n,cmp);
for(i=0;i<n;i++){
if(house[i].f<=m){
m-=house[i].f;
s+=house[i].j;
}
else if(house[i].f>m&&m>0){
s+=m*house[i].rate;
break;
}
}
cout<<fixed<<setprecision(3)<<s<<endl;
}
return 0;
}
这是我做作业时的一道题,这道题思路很简单,就是求仓库各个房间换取猫粮的性价比,然后排序,若剩余猫粮数大于仓库所需猫粮数,可获得整个仓库的爪哇豆,最后面若猫粮数小于仓库所需猫粮书,就将剩余猫粮数乘性价比。但提交时却遇到了种种错误。首先求性价比要用到除法,提交时显示Runtime Error(INTEGER_DIVIDE_BY_ZERO)的错误,最后知道这是进行整数除法时出现了除数为零的异常,我将整型改为实型后,便不会发生这个错误。除法运算会遇到种种错误,因此当某道题目能用乘法运算时,尽量不要用除法。这道题目要求输出多个案例,当要输出多个案例时可以用while(scanf("%d,&n)!=EOF)或while(cin>>n)来实现。
2:
一个人要写作业,但是每次只能做一个,每个作业都有对应的截止时间,如果过了截止时间就会扣相应的分数,求扣的最小分数。
输入:第一行输入多组测试用例t,下面的一行输入有几门作业n,再下面一行对应的这n门作业的截止时间,再下面一行对应的是n门作业的过了截止时间扣的分数。
输出:扣的最小分数
代码
#include<iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct wu {
int li,date;
bool flag;
};
bool cmp( wu a, wu b) {
if(a.date!=b.date) return a.date<b.date;
else return a.li >b.li;
}
int main() {
int n,i;
while(scanf("%d",&n)!=EOF)
{ wu a[10000];
int Li=0;
for(i=0; i<n; i++) {
cin>>a[i].li>>a[i].date;
Li+=a[i].li;
a[i].flag=false;
}
sort(a,a+n,cmp);
int s=0,DATE=0;
for(i=0; i<n; i++) {
if(a[i].date>DATE) {
DATE++;
continue;
}
int pos = i,tmpScore = a[i].li;
for(int j=0; j<i; j++) {
if(a[j].li<tmpScore && !a[j].flag) {
tmpScore = a[j].li;
pos = j;
}
}
s+=tmpScore;
a[pos].flag = true;
}
cout<<Li-s<<endl;
}
return 0;
}
起初我把这道题想得很简单,只是将各作业的截止日期升序排列,截止日期相同的再按分数降序排列。然后从第一个开始循环,若某作业的截止日期大于当前日期,便不丢分,当前日期递增,若小于,则丢分。提交后显示wrong answer,这才知道自己做错了。这道题的关键在于,后面舍弃的作业的分数可能比前面选择的作业的分数要高,为了尽可能失去较少的分数,要将两者进行替换。
做作业遇到或解决的问题
- long long 定义的元素要放在主函数外面。
- 好几个题不能ac,提示presentation error。这是因为答案的输出不够标准,答案结尾多了或少了空格或回车。例如"cout<<s;"提示错误,改成"cout<<s<<endl;"后便正确。
- 好几次因为数组范围太小而显示runtime error错误。所以在审看题时,一定要认真审题,一定要注意元素的范围,输入输出格式、小数等。
感悟
贪心算法实现的最优解时由局部最优解一步步递进产生,它有它的局限性,它不能对所有问题都能得到整体最优解。
贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只于当前状态有关。
做作业时,对于某些问题审完题,经过一些思考,自己有了一定的思路,但写出代码后却很难ac,有些时候,改错误的时间要比有了思路的时间多得多。因此,学acm必须要有做够的耐心。而且自己对于某道题的思路与一些题解相比,往往显得麻烦的多。所以如果一道题ac了,也要查询不同方法,找寻最简单的择善而从。总之,困难是必然的,面对困难要有足够的耐心才能不断进步。相信自己能勇往直前,不断进步!