最大报销额

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;
bool dp[3333333];
int main (void)
{
    int n,m,mm,s,i,j;
    double Q,d,x[1111];
    char c,q;
    while(cin>>Q>>n&&n)
    {
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        mm=Q*100;
        for(i=0;i<n;i++)
        {
            cin>>m;
            s=0;
            memset(x,0,sizeof(x));
            while(m--&&cin>>c>>q>>d)
            {
                x[c]+=d;
                s+=d*100;
                if(x[c]>600||c<‘A‘||c>‘C‘)s+=100000;//单个超过600或者不是A,B,C直接加上最大值
            }
            if(s<=100000)//判断发票是否有效，因为最多不能超过1000，用100倍是考虑实数两位小数的精度
            {
                for(j=mm;j>=s;j--)	//01背包
                if(dp[j-s])dp[j]=1;
            }
        }
        while(!dp[mm])mm--;
        printf("%.2lf\n",mm/100.0);
    }
    return 0;
}

HDU--杭电--1864--最大报销额--01背包,布布扣,bubuko.com

HDU--杭电--1864--最大报销额--01背包

原文：http://blog.csdn.net/jingdianitnan/article/details/21158795