最大报销额

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

123.50
1000.00
1200.50

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int v[35],dp[3000000+5];

int main(){
    double P,n;
    while(cin>>P>>n && n){
        P*=100;
        int i,j,m,a,b,c,flag;
        for(i=1;i<=n;i++){
            double p;
            char ch,cc;
            cin>>m;
            a=b=c=flag=0;
            for(j=1;j<=m;j++){
                scanf("%c%c:%lf",&cc,&ch,&p);
                p*=100;

                if(ch=='A') a+=p;
                else  if(ch=='B')  b+=p;
                else  if(ch=='C')  c+=p;
                else  flag=1;
            }

            if(!flag&&a+b+c<=100000&&a<=60000&&b<=60000&&c<=60000)
                v[i]=a+b+c;
            else  v[i]=P+1;
        }

        memset(dp,0,sizeof dp);
        for(i=1;i<=n;i++)
            for(j=P;j>=v[i];j--)
            dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
        printf("%.2lf\n",dp[(int)P]/100.0);
    }
    return 0;
}

hdu 1864 最大报销额 DP

原文：http://blog.csdn.net/hyccfy/article/details/42833761