非常裸的01背包，水题。注意控制精度
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int INF = 1e6;
using namespace std;
int dp[4*INF],cost[5],w[31];
int max(int x,int y)
{
if(x > y)
return x;
else
return y;
}
int min(int x,int y)
{
if(x > y)
return y;
else
return x;
}
int main()
{
double z; int n,zong,m;
char mm;
while(~scanf("%lf%d",&z,&n))
{
if(n==0) break;
zong = z * 100; int l = 1;
memset(w,0,sizeof(w));
for(int i = 1;i<=n;i++)
{
scanf("%d",&m);
int sum = 0;
memset(cost,0,sizeof(cost));
int flag = 1;
for(int j = 0;j<m;j++)
{
scanf(" %c:%lf",&mm,&z);
if(mm=='A') cost[1] += z * 100;
else if(mm=='B') cost[2] += z * 100;
else if(mm=='C') cost[3] += z * 100;
else flag = 0;
}
if(!flag)
continue;
if(cost[1]<=60000 &&cost[2]<=60000 &&cost[3]<=60000)
sum += cost[1]+cost[2]+cost[3];
if(sum<=10000000)
{
w[l++] = sum;
// cout<<"w[l]="<<w[l-1]<<endl;
}
}
memset(dp,0,sizeof(dp));
for(int i = 1;i<=l;i++)
{
for(int j = zong;j>=w[i];j--)
{
if(dp[j]<dp[j-w[i]]+w[i])
dp[j] = dp[j-w[i]]+w[i];
}
}
printf("%.2lf\n",dp[zong]*1.0/100);
}
return 0;
}