最大报销额

  这道题有两个需要注意的地方：一是题目说的“每项”其实是“每类”，也就是A类,B类和C类，而不是每个物品......(这题目表述有问题啊！)；二是在计算时要将所有的数据扩大100倍然后再转为int，计算出最后结果后再缩小为原来的倍率，否则无法用钱数来做背包(浮点数无法作为数组下标)。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
double dp[3000005];
int m[35];
int main()
{
    double q;int n;
    while(cin>>q>>n)
    {    
        if(n==0)        break;
        q*=100;
        int qtmp=(int)q;
        memset(dp,0,sizeof(dp));memset(m,0,sizeof(m));
        bool flag;int idx=0;
        for(int i=0;i<n;i++)
        {    
            double sum=0;
            char ch;double a,b,c,tmp;
            int num;
            flag=1;
            cin>>num;getchar();
            a=b=c=0;
            while(num--)
            {    
                tmp=0;
                scanf("%c:%lf",&ch,&tmp);char c=getchar();
                tmp*=100;
                if(ch=='A')
                    a+=tmp;
                else if(ch=='B')
                    b+=tmp;
                else if(ch=='C')
                    c+=tmp;
                else
                    flag=0;
                if(flag)
                    sum+=tmp;
            }
            if(sum>100000||a>60000||b>60000||c>60000)
                flag=0;
            if(flag)
                m[idx++]=(int)sum;
        }
        for(int i=0;i<=idx;i++)
            for(int j=qtmp;j>=m[i];j--)
                dp[j]=max(dp[j],dp[j-m[i]]+m[i]);
        printf("%.2lf\n",dp[qtmp]/100.0);
    }
    return 0;
}