HDU - 1864 最大报销额 （01背包）

题意：现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（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\n", dp[len - 1]);

    }

    return 0;

}