链接：

题意：现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单类物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

题解：处理出可以报销的发票的数组 a[] 。

　　　定义：dp[i] 为报销第 i 个发票的情况下报销的最大值；

　　　状态转移：dp[i] = max( dp[i],  dp[0 ~ i-1] + a[i]);

#include 
     
      using namespace std;const double EPS = 1e-6;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;const int maxn = 30 + 10;double Q;int n, m;double a[maxn];double dp[maxn];int main(){    while(scanf("%lf%d", &Q, &n) != EOF && n){        memset(a, 0, sizeof(a));        memset(dp, 0, sizeof(dp));        int cnt = 1;        for(int i = 0; i < n; i++){            scanf("%d", &m);            bool ok = true;            char kind; double A = 0, B = 0, C = 0, p;            for(int i = 0; i < m; i++){                scanf(" %c:%lf", &kind, &p);                if(kind < 'A' || kind > 'C' || p > 600) ok = false;                else if(kind == 'A') A += p;                else if(kind == 'B') B += p;                else if(kind == 'C') C += p;            }            if(A > 600 || B > 600 || C > 600 || A + B + C > min(1000.0, Q)) ok = false;            if(ok) a[cnt++] = A + B + C;        }        for(int i = 1; i < cnt; i++){            for(int j = i - 1; j >= 0; j--){                if(dp[j] + a[i] <= Q){                    dp[i] = max(dp[i], dp[j] + a[i]);                }            }        }        double ans = 0;        for(int i = 1; i < cnt; i++) ans = max(ans, dp[i]);        printf("%.2f\n", ans);    }    return 0;}