题解 | #最大报销额#

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main() {
    double Q;
    int N;
    while (cin >> Q >> N) {
        if (N == 0) break;
        vector<int> billPrice(N+1);
        billPrice[0]=0;
        int count = 0; //统计有效的票数
        //筛选有效发票
        for (int i = 0; i < N; i++) {
            int k;
            int price = 0;
            bool flag = true;//是否有效
            string temp;
            cin >> k;
            for (int i = 0; i < k; i++) {
                cin >> temp;
                if (temp[0] == 'A' || temp[0] == 'B' || temp[0] == 'C') {
                    string pds = temp.substr(2);
                    int pd = stod(pds)*100;
                    if (pd > 60000) {
                        flag = false;
                    }
                    price = price + pd;
                } else {
                    flag = false;//不符合种类
                }
            }
            if (price > 100000) flag = false; //超出条件
            if (flag) billPrice[1+count++] = price; //符合要求加入数组,第n个发票对应下标n
        }
        //背包问题
        vector<vector<int>> dp(count + 1, vector<int>(Q*100 + 1, 0));
        for (int i = 1; i <= count; i++) {
            for (double j = 1; j <= Q*100;j++) {
                if (j >= billPrice[i]) {
                    dp[i][j] = max(dp[i - 1][j],
                                   dp[i - 1][j - billPrice[i]] + billPrice[i]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        printf("%.2f\n",dp[count][Q*100]*1.0/100);
    }
}
// 64 位输出请用 printf("%lld")