01 背包
每一种发票，要么拿，要么不拿
本题要点：
1、判断发票的有效性（每次报销，都有一个最大报销额度 max_val）:
（a） 发票的总价值不能超过 1000 或 max_val
（b） 发票的单类型报销额度不能超过 600
（c） 类型只能是 ‘A’, ‘B’, ‘C’。出现其他类型，次发票无效。
2、解决了发票的有效性，后面就是套用 01 背包的模板。 n 张发票，看做是n个物品，每个物品的体积为1.
然后有一个背包容量大小是 n 的背包，从n个物品中取若干个，得到的最大价值是多少。 有个附加条件，
这个最大价值不能超过 最大报销额度 max_val。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 40;
double bills[MaxN]; // 有效的发票
double f[MaxN][MaxN]; // f[i][j] 表示从前i张发票中，选出j张，获得的最大价值
int cnt; //有效的发票数量
int n;
double max_val;struct Bill
{
double a, b, c;Bill():a(0), b(0), c(0){
}
};void solve()
{
memset(f, 0xcf, sizeof f);f[0][0] = 0;for(int i = 1; i <= cnt; ++i){
for(int j = 0; j <= cnt; ++j)f[i][j] = f[i - 1][j];for(int j = 1; j <= cnt; ++j){
if(f[i - 1][j - 1] + bills[i] <= max_val) // 附加条件，不能大于 max_valf[i][j] = max(f[i][j], f[i - 1][j - 1] + bills[i]);}}double ans = 0;for(int i = 1; i <= cnt; ++i){
ans = max(f[cnt][i], ans);}printf("%.2f\n", ans);
}int main()
{
int k;char ch;double val;while(scanf("%lf%d", &max_val, &n) != EOF && n){
cnt = 0;for(int i = 0; i < n; ++i){
scanf("%d", &k);Bill b;bool valid = true; // 发票的有效性, 判断字母是否都是 A B Cfor(int j = 0; j < k; ++j){
getchar();ch = getchar();if(ch != 'A' && ch != 'B' && ch != 'C') valid = false;getchar();scanf("%lf", &val);if(valid){
if('A' == ch) {
b.a += val;}else if('B' == ch){
b.b += val;}else{
b.c += val;}}}if(valid){
if(b.a + b.b + b.c > 1000 || b.a + b.b + b.c > max_val)valid = false;if(b.a > 600 || b.b > 600 || b.c > 600)valid = false;if(valid)bills[++cnt] = b.a + b.b + b.c;}}// test();solve();}return 0;
}/* 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 */