HDU 1864 最大报销额 背包问题

分析：虽然看上去就知道是一个背包问题，但是，数据都是小数，而且只有两个小数，如果把每个数都*100再取整，这样的话，就可以放心用背包了，而且不会丢失数据．

注意：题中有个"单项物品的价值不得超过600元"中的"单项"是指一类，当时我就被这误导了，WA好多次．

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 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 for( int j=qq; j>=f[i]; --j )
if(dp[j] dp[j]=dp[j-f[i]]+f[i];
printf("%.2lf\n",dp[qq]/100.0);
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
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 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 for( int j=qq; j>=f[i]; --j )
if(dp[j] dp[j]=dp[j-f[i]]+f[i];
printf("%.2lf\n",dp[qq]/100.0);
}
return 0;
}