HDU-1864：最大报销额（浮点数01背包）

链接：HDU-4055：最大报销额

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

const double EPS = 1e-;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

const int maxn =  + ;

double Q;

int n, m;

double a[maxn];

double dp[maxn];

int main()

{

    while(scanf("%lf%d", &Q, &n) != EOF && n){

        memset(a, , sizeof(a));

        memset(dp, , sizeof(dp));

        int cnt = ;

        for(int i = ; i < n; i++){

            scanf("%d", &m);

            bool ok = true;

            char kind; double A = , B = , C = , p;

            for(int i = ; i < m; i++){

                scanf(" %c:%lf", &kind, &p);

                if(kind < 'A' || kind > 'C' || p > ) ok = false;

                else if(kind == 'A') A += p;

                else if(kind == 'B') B += p;

                else if(kind == 'C') C += p;

            }

            if(A >  || B >  || C >  || A + B + C > min(1000.0, Q)) ok = false;

            if(ok) a[cnt++] = A + B + C;

        }

        for(int i = ; i < cnt; i++){

            for(int j = i - ; j >= ; j--){

                if(dp[j] + a[i] <= Q){

                    dp[i] = max(dp[i], dp[j] + a[i]);

                }

            }

        }

        double ans = ;

        for(int i = ; i < cnt; i++) ans = max(ans, dp[i]);

        printf("%.2f\n", ans);

    }

    return ;

}