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;
}