AOJ 524.桂园食堂

228


Description  


食堂对大家来说一点都不陌生,每次打菜的时候我们几乎看重两样:价钱和味道.现在你来到了桂园二楼打菜,假设你的卡里的钱为m,现在食堂里有n种菜,每种菜的价格分别为Pi,用Li来衡量你心中的每种菜的味道,我们称之为满意值.那你本次打菜最满意的值是多少呢 假设你的饭量足够大,并且你不会打两份一样的菜.



Input  


有多组测试数据,对于每组数据
第一行:n m为一个整数和一个一位小数(即小数点后只保留一位)分别代表菜的种类和你的卡里的钱(0<=n<=100,0<=m<=1000)
接下来有n行,每行代表两个一位小数Pi和Li(0<=Pi<=10,0<=Li<=10)
输入到文件结束


Output  


每组数据输出一个一位小数,代表最大满意值


Sample Input  


2 10.0
1.5 9.9
3.5 8.0
3 2.0
1.5 9.0
2.0 8.8
2.5 0.0


Sample Output  


17.9
9.0


题解


模板题,01背包问题
注意考虑浮点误差

代码


/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn = 10005;
double dp[maxn];
int v;

void ZeroOnePack(int cost,double weight) {
for(int i = v; i >= cost; i--)
dp[i] = max(dp[i],dp[i - cost] + weight);
}

bool Do() {
int n,m;
double mt;
if(scanf("%d%lf",&n,&mt) == EOF)
return false;

m = (int)(mt * 10+0.5);
v = m;
memset(dp,0,sizeof(dp));

for(int i = 1;i <= n;i++) {
double p,l;
scanf("%lf%lf",&p,&l);
ZeroOnePack((int)(p*10+0.5),l);
}

printf("%.1f\n",dp[m]);
return true;
}

int main() {
while(Do());
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论