学步园

每张发票要么报销要么不报销，0-1背包

#include<iostream>
using namespace std;
int m,n,dp[3000002],a[35],p[3];
int max(int a,int b)
{
    if(a>b)return a;
    return b;
}
int main()
{
    int i,j,v,k,flag;
    double b,c;
    char ch;
    while(scanf("%lf%d",&b,&n),n)
    {
        v=(int)(b*100);j=0;//数据都乘以100转化成整数
        for(i=1;i<=n;i++)
        {
            scanf("%d",&k);
            p[0]=p[1]=p[2]=0;
            flag=1;
            getchar();
            while(k--)
            {
                scanf("%c:%lf",&ch,&c);
                getchar();
                 if(ch>='A'&&ch<='C')
                    p[ch-'A']+=(int)(c*100);
                    else flag=0;
            }
            if(p[1]<=60000&&p[0]<=60000&&p[2]<=60000&&p[1]+p[2]+p[0]<=100000&&flag)//去掉不符合的数据
                a[j++]=p[0]+p[1]+p[2];
        }
        n=j;
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            for(j=v;j>=a[i];j--)
                dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
            printf("%.2f\n",dp[v]*1.0/100);       
    }
    return 0;
}