1045: 最大报销额

时间限制: 1 Sec  内存限制: 32 MB
提交: 17  解决: 9
[提交][状态][讨论版]

题目描述

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

输入

    测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（N<=30）是发票张数。随后是 N 行输入，每行的格式为：
    m Type_1:price_1 Type_2:price_2 ... Type_m:price_m
    其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。

输出

    对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。

样例输入

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 }