2021-03-20

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,这才知道自己做错了。这道题的关键在于,后面舍弃的作业的分数可能比前面选择的作业的分数要高,为了尽可能失去较少的分数,要将两者进行替换。

做作业遇到或解决的问题

  1. long long 定义的元素要放在主函数外面。
  2. 好几个题不能ac,提示presentation error。这是因为答案的输出不够标准,答案结尾多了或少了空格或回车。例如"cout<<s;"提示错误,改成"cout<<s<<endl;"后便正确。
  3. 好几次因为数组范围太小而显示runtime error错误。所以在审看题时,一定要认真审题,一定要注意元素的范围,输入输出格式、小数等。

感悟

贪心算法实现的最优解时由局部最优解一步步递进产生,它有它的局限性,它不能对所有问题都能得到整体最优解。
贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只于当前状态有关。
做作业时,对于某些问题审完题,经过一些思考,自己有了一定的思路,但写出代码后却很难ac,有些时候,改错误的时间要比有了思路的时间多得多。因此,学acm必须要有做够的耐心。而且自己对于某道题的思路与一些题解相比,往往显得麻烦的多。所以如果一道题ac了,也要查询不同方法,找寻最简单的择善而从。总之,困难是必然的,面对困难要有足够的耐心才能不断进步。相信自己能勇往直前,不断进步!

上一篇:生产者消费者模型


下一篇:213. House Robber II-动态规划-打家劫舍系列2