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

测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，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位。

​

​

思路

本题作为2007年浙大计算机研究生复试上机考试题个人认为是非常成功的，因为很多细节点需要去把握。

本题属于简单的0-1背包，但是前面的细节限制很容易出错：

  • 只有A，B，C三种类型的发票，如测试数据一中的X发票就不报销
  • 物品单项的报销额不超过600，如测试数据一第三张发票两个A类需要累加后计算
  • 每张发票总额不超过1000

除了限制条件外，还有一些需要处理的点：

  • 报销额都为保留两位小数的浮点数，遍历起来不方便，可以采取都乘100，最后结果除100的方式来处理。
  • 数据输入处理很麻烦，可以用%*c来过滤空格

解决完这些问题，剩下就是0-1背包了。

​

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 3000050;//发票张数30*每张总额1000*放大倍数100 = 3000000
int dp[MAXN];

struct node{
    int m;
    int sum=0;
} invoice[35];

int main(){
    double Q;
    int q;
    int N;
    char ch;
    double y;
    int a,b,c,t;
    bool flag;
    while(scanf("%lf%d",&Q,&N)!=EOF && N){
        q = (int)(Q * 100);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < N; i++){
            scanf("%d", &invoice[i].m);
            a = b = c = 0;
            flag = true;
            for (int j = 0; j < invoice[i].m; j++){
                scanf("%*c%c:%lf", &ch, &y);
                t = (int)(y * 100.0);
                if(ch == 'A')
                    a += t;
                else if(ch=='B')
                    b += t;
                else if(ch=='C')
                    c += t;
                else
                    flag = false;
            }
            if(a+b+c<=100000 && a<=60000 && b <= 60000 && c <= 60000 && flag)
                invoice[i].sum = a + b + c;
            else
                invoice[i].sum = q + 1;
        }
        for (int i = 0; i < N; i++){
            for (int j = q; j >= invoice[i].sum; j--){
                dp[j] = max(dp[j], dp[j - invoice[i].sum] + invoice[i].sum);
            }
        }
        printf("%.2lf\n", (dp[q] / 100.0));
    }
    return 0;
}