200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0
123.50 1000.00 1200.50
1 #define _CRT_SECURE_NO_DEPRECATE
2 #include<iostream>
3 #include<algorithm>
4 #include<stdio.h>
5 using namespace std;
6
7 double money[32];
8 double dp[32];
9 /*这里有多张发票，针对不同的金额的发票存在一个选择的问题，因为总量一定，所以要使用
10 动态规划来寻求最优解。对每一张合格的发票，进行判断是否应该要报销，并记录下来
11 */
12
13 int main(){
14 double Q;
15 int N;
16 while (cin >> Q >> N && N != 0){
17 int m;
18 int k = 0;
19 for (int i = 0; i < 32; i++){
20 money[i] = 0;
21 dp[i] = 0;
22 }
23 for (int i = 1; i <= N; i++){
24 cin >> m;
25 double total = 0;
26 bool flag = false;
27 for (int j = 1; j <= m; j++){
28 char type;
29 double price;
30 getchar();
31 scanf("%c:%lf", &type, &price);//这种输入法
32 if (price > 600 || type<‘A‘ || type>‘C‘){//单张发票里面有单项价格
33 //大于600，或者不在报销类别里面的项，该发票就不能报销
34 flag = true;
35 break;
36 }
37 total += price;
38 }
39 if (!flag && total <= 1000 && total <= Q){
40 money[k] = total;
41 k++;
42 }
43 }
44 for (int i = 1; i <= k; i++){
45 if (i == 1){
46 dp[i] = money[0];
47 }
48 else{
49 if (dp[i - 1] + money[i - 1] <= Q){
50 dp[i] = max(dp[i - 1], dp[i - 1] + money[i - 1]);
51 }
52 else{
53 dp[i] = dp[i - 1];
54 }
55 }
56 }
57
58 printf("%.2f\n", dp[k]);
59 }
60 return 0;
61 }
1045: 最大报销额（2007年浙江大学计算机及软件工程研究生机试真题 ）
原文：https://www.cnblogs.com/tangyimin/p/10546663.html