HDU 1009

很简单的一道贪心算法的题，就是背包问题换个叫法，注意输出的精度即可！！！

AC 代码：

#include <iostream>
    #include <stdlib.h>
    #include <algorithm>
    #include <iomanip>

    using namespace std;

    struct bag{
        int w; //每个房间的Javabean的数量
        int v; //交换时需要的cat food
        double w_v; //性价比
    };

    //实现降序排列
    bool cmp(bag x,bag y){
        return x.w_v>y.w_v;
    }

    int main(){
        bag *b;
        //n个房间，cat food总量为m
        int n,m;
        while(cin>>m>>n){
            b = new bag[n];
            //struct bag b[n];
            if(n==-1 && m==-1)
                break;
            for(int i=0;i<n;i++){
                cin>>b[i].w>>b[i].v;
                b[i].w_v=(double)b[i].w/b[i].v;
            }
            sort(b,b+n,cmp);
            double maxW=0;
            for(int i=0;i<n;i++){
                if(b[i].v<=m){
                    maxW+=b[i].w;
                    m-=b[i].v;
                }else{
                    //这里要按比例交换
                    maxW+=((double)m/b[i].v)*b[i].w;
                    m=0;
                    break;
                }
            }
            //控制输出的精度
            cout <<setiosflags(ios::fixed)<<setprecision(3)<<maxW<< endl;
        }
        return 0;
    }
    /*
    5 3
    7 2
    4 3
    5 2
    20 3
    25 18
    24 15
    15 10
    -1 -1
    13.333
    31.500
    */

运行结果

？代码里我用bag *b; b = new bag[n];时就可以AC，用struct bar b[n]时就会由编译错误，不知道咋回事