这道题属于简单的01背包，但是背包问题还算简单，就是前面的细节处理的时候要注意，题意大致说了三条限制吧
1. 只有a, b, c 三种类型的发票可以报销，其它的一律不报销
2. 物品单项的报销额不超过600
3. 每个发票总额不超过1000
有了这三个，还有一个要小心的就是报销额可以为浮点数，所以这里有个小技巧，就是将它乘100，到最后再除以100， 为什么要乘100呢， 因为最后要求保留两位小数
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int dp[];//发票张数30*每张总额1000*放大倍数100 = 3000000
int main()
{
char ch;
double x, y;
int sum, a, b, c, money[], t;
int n, k;
while (~scanf("%lf %d", &x, &n) && n)
{
sum = (int)(x * );//将背包的容量放大为整数(这里就是报销的最大值)
memset(dp, , sizeof(dp));
memset(money, , sizeof(money));
int len = ;//可报销的列表长度，也就是最后的n
for (int i = ; i < n; i++)
{
scanf("%d", &k);
a = b = c = ;//分别来保存a类型,b类型,c类型
bool flag = true;
while (k--)
{
scanf(" %c:%lf", &ch, &y);
t = (int)(y * );
if (ch == 'A' && a + t <= )
a += t;
else if (ch == 'B' && b + t <= )
b += t;
else if (ch == 'C' && c + t <= )
b += t;
else
flag = false; }
if (a + b + c <= && a <= && b <= && c <= && flag)
money[len++] = a + b + c;//如果满足以上三个条件
}
for (int i = ; i < len; i++)//01背包核心代码
{
for (int j = sum; j >= money[i]; j--)
if (dp[j] < dp[j - money[i]] + money[i])
dp[j] = dp[j - money[i]] + money[i];
}
printf("%.2f\n", (dp[sum]/100.0));
}
return ;
}