3611: 生日礼物-训练套题T5T4
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：1
Description
4.生日礼物 (gift. pas)
【问题描述】
Kobe有N元钱，M个商品可以选择，每个商品有一定的价格P。他对每个商品有不同的满意度F，希望在花费不超过N元的情况下，使得买到的商品的满意度总和最大。
【输入文件】
第一行为N，第二行为M
第三行到第M+2行为两个数，分别为商品的价格P和满意度F
【输出文件】
买到的商品的最大满意度总和.
【样例输入】
47.13
4
17.11 2
11.48 1
18.42 2
30.01 2
【样例输出】
5
【数据规模】
对于40%的数据有：
0<=N<=100且N小数点后有两位小数
1<=M<=100
对于100%的数据有：
0<=N<=10000且N小数点后有两位小数
1<=M<=10000
1<=F<=2且F为整数
0<=P<=100且P小数点后有两位小数
HINT
1.放大100倍。
2.注意到0、1背包超时。
3.注意到F只有1和2两种值。 特别要关注数据范围异常的数据。
4.将物品按F分为两种，分别按价格从小到大的顺序排序。
对于F=1，价格依次为1,3,4,7，则贪心 f[1]=1,f[2]=1,f[3]=1,f[4]=2,f[5]=2,f[6]=2,f[7]=2,f[8]=3...f[15]=4
对于F=2，价格依次为2,3,4,5，则贪心g[1]=0,g[2]=2,g[3]=2,g[4]=2,g[5]=4...g[9]=6....g[14]=8
opt[i]=max{f[k]+g[i-k]}