hdu1864——最大报销额

现有一笔经费可以报销一定额度的***。允许报销的***类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张***的总额不得超过1000元，每张***上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆***中找出可以报销的、不超过给定额度的最大报销额。
Input
测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（<=30）是***张数。随后是 N 行输入，每行的格式为：
m Type_1:price_1 Type_2:price_2 … Type_m:price_m
其中正整数 m 是这张***上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。
Output
对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。
Sample Input
200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0
Sample Output
123.50
1000.00
1200.50

这题就是输入处理加浮点数的01背包
几个坑点，一是这个读取的问题，主要要格式化读入，前面加个空格，二是项目总额不能超过600是指所有A 所有B 这样每一向加起来不能超过600 误认为是每一小项不能超过600 然后就是浮点数的处理，看了一个博客将所有浮点数*100得到整数来进行dp 这样子数组要开大100倍 不过在这题还可以

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
double q;
int n;
int w[50];
int dp[4000010];
int main(void){
    //freopen("data.txt","r",stdin);
    while(~scanf("%lf%d",&q,&n) && n){
        memset(w,0,sizeof(w));
        memset(dp,0,sizeof(dp));
        int cnt=0;
        for(int i=0;i<n;i++){
            int num;
            scanf("%d",&num);
            char t;
            double x;
            int sum=0;
            int flag=0;
            int ta=0;
            int tb=0;
            int tc=0;
            for(int j=0;j<num;j++){
                scanf(" %c:%lf",&t,&x);
                //printf("%c---%lf\n",t,x);
                x=(int)(x*100);
                if(!flag){
                    if(t=='A'){
                        ta+=x;
                        if(ta>60000){
                            flag=1;
                        }
                    }
                    else if(t=='B'){
                        tb+=x;
                        if(tb>60000){
                            flag=1;
                        }
                    }
                    else if(t=='C'){
                        tc+=x;
                        if(tc>60000){
                            flag=1;
                        }
                    }
                    else{
                        flag=1;
                    }
                }
            }
            sum=ta+tb+tc;
            if(sum>100000){
                flag=1;
            }
            if(!flag){
                w[cnt++]=sum;
            }
        }
        for(int i=0;i<cnt;i++){
            for(int j=(int)(q*100);j>=w[i];j--){
                dp[j]=max(dp[j],dp[(int)(j-w[i])]+w[i]);
            }
        }
        printf("%.2lf\n",dp[(int)(q*100)]*1.0/100);
    }
    return 0;
}