Saving HDU

点我挑战题目

题意分析

给出来背包容量v和物品数量n，接下来n行分别给出每个商品单位体积的价值和物品总共的体积(注意是单位体积，不是每个物品）。求出最多能装多少价值的物品。

典型的贪心策略。

按单价排序，优先装单价高的，之后装单价低的。装满为止即可。最后算出总价值输出。

代码总览

/*

    Title:HDOJ.2111

    Author：pengwill

    Date: 2016-11-22

*/

#include <iostream>

#include <stdio.h>

#include <algorithm>

using namespace std;

struct bb{

    int val;

    int v;

    //double rate;

}item[105];

int cmp(bb a, bb b)

{

    return a.val>b.val;

}

int main()

{

    int tj;

    while(scanf("%d",&tj)!= EOF && tj){

        int n,i;

        scanf("%d",&n);

        for(i = 0;i<n;++i){

            scanf("%d %d",&item[i].val,&item[i].v);

            //item[i].rate = item[i].val / item[i].v;

        }

        sort(item,item+n,cmp);

        int ret = 0;

        for(i = 0;i<n;++i){

            if(item[i].v<=tj){

                ret+=item[i].val * item[i].v;

                tj-=item[i].v;

            }else{

                ret+= tj*item[i].val;

                tj = 0;

            }

            if(!tj){

                break;

            }

            item[i].val = item[i].v  = 0;

        }

        printf("%d\n",ret);

    }

    return 0;

}