题意：现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。
分析：dp[i]---截止到第i张发票可得到的最大报销额。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-8;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 30000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
vector<double> v;
double dp[MAXN];
int main(){
double Q;
int N;
while(scanf("%lf%d", &Q, &N) == 2){
if(N == 0) return 0;
v.clear();
for(int i = 0; i < N; ++i){
int k;
scanf("%d", &k);
bool ok = true;
double A, B, C;
A = B = C = 0;
for(int j = 0; j < k; ++j){
char c;
double p;
scanf(" %c:%lf", &c, &p);
if(!ok) continue;
if(c != 'A' && c != 'B' && c != 'C'){
ok = false;
continue;
}
if(c == 'A') A += p;
else if(c == 'B') B += p;
else C += p;
}
if(A + B + C > 1000 || A > 600 || B > 600 || C > 600){
ok = false;
continue;
}
if(ok){
v.push_back(A + B + C);
}
}
memset(dp, 0, sizeof dp);
int len = v.size();
for(int i = 0; i < len; ++i){
dp[i] = v[i];
for(int j = 0; j <= i - 1; ++j){
if(dp[j] <= Q){//第i张不选
dp[i] = max(dp[i], dp[j]);
}
if(dp[j] + v[i] <= Q){//第i张选
dp[i] = max(dp[i], dp[j] + v[i]);
}
}
}
printf("%.2f
", dp[len - 1]);
}
return 0;
}