HDU 1864 最大報銷額 背包問題

分析：雖然看上去就知道是一個背包問題，但是，數據都是小數，而且只有兩個小數，如果把每個數都*100再取整，這樣的話，就可以放心用背包了，而且不會丟失數據．

注意：題中有個"單項物品的價值不得超過600元"中的"單項"是指一類，當時我就被這誤導了，WA好多次．

[cpp] 
#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
#include<cctype>  
#include<iomanip>  
#include<queue>  
using namespace std; 
 
const int maxn=5000000; 
int f[50]; 
int dp[maxn]; 
 
int main(){ 
    double Q;  int n; 
    while(cin>>Q>>n&&n){ 
        int qq=Q*100,t=0; 
        for(int i=0,q=1,m; i<n; ++i,q=1){ 
            double s=0; 
            cin>>m; 
            double c[3]={0,0,0}; 
            while(m--){ 
                getchar(); 
                char a; double b; scanf("%c:%lf",&a,&b); 
                if((a!='A'&&a!='B'&&a!='C')||b>600.0)q=0; 
                if(a=='A')c[0]+=b; 
                if(a=='B')c[1]+=b; 
                if(a=='C')c[2]+=b; 
                s+=b; 
            } 
            if(c[0]>600.0||c[1]>600.0||c[2]>600.0)q=0; 
            if(s>1000.0||s>Q||s<=0)q=0; 
            if(q) f[t++]=s*100; 
        } 
        memset(dp,0,sizeof(dp)); 
        for( int i=0; i<t; ++i ) 
            for( int j=qq; j>=f[i]; --j ) 
                if(dp[j]<dp[j-f[i]]+f[i]) 
                    dp[j]=dp[j-f[i]]+f[i]; 
        printf("%.2lf\n",dp[qq]/100.0); 
    } 
    return 0; 
} 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<iomanip>
#include<queue>
using namespace std;

const int maxn=5000000;
int f[50];
int dp[maxn];

int main(){
    double Q;  int n;
    while(cin>>Q>>n&&n){
        int qq=Q*100,t=0;
        for(int i=0,q=1,m; i<n; ++i,q=1){
            double s=0;
            cin>>m;
            double c[3]={0,0,0};
            while(m--){
                getchar();
                char a; double b; scanf("%c:%lf",&a,&b);
                if((a!='A'&&a!='B'&&a!='C')||b>600.0)q=0;
                if(a=='A')c[0]+=b;
                if(a=='B')c[1]+=b;
                if(a=='C')c[2]+=b;
                s+=b;
            }
            if(c[0]>600.0||c[1]>600.0||c[2]>600.0)q=0;
            if(s>1000.0||s>Q||s<=0)q=0;
            if(q) f[t++]=s*100;
        }
        memset(dp,0,sizeof(dp));
        for( int i=0; i<t; ++i )
            for( int j=qq; j>=f[i]; --j )
                if(dp[j]<dp[j-f[i]]+f[i])
                    dp[j]=dp[j-f[i]]+f[i];
        printf("%.2lf\n",dp[qq]/100.0);
    }
    return 0;
}