hdu 1864 最大报销额 01背包

缘起

日常浪费生命~ hdu 1864 最大报销额

分析

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
现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（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位。

【样例输入】
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

【限制】
1s

【来源】
浙大计算机研究生复试上机考试-2007年

此题什么数据范围都没有给, 可以看得出, 题目出的极为业余和随意~

因为只允许报销A、B、C 三种类型的发票, 所以如果包含X报销项的发票直接淘汰~ 除此之外, 发票的总额超过1000元的，每张发票上，单项物品的价值超过600元的都直接淘汰~

其实每张发票只有选与不选, 所以显然是一个01背包问题,但是这里的是浮点数, 所以要乘以100才行（元转换为分）

1
2
3
令 dp[i][j]表示前i张发票, 是否可以表达j分钱（即本题又是容量=价值的01背包）
则熟悉的dp模型
dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]]

于是不难写下如下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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const double eps = 1e-8;
const int maxv = 3000005; //不超过30张发票,每张不超过1000元(100000分),所以总共的容量<=3000000
double vv;
int V, n;
bool dp[maxv];

void zo(int c)
{
	for (int v = V; v>=c; v--)
	{
		dp[v] = dp[v] || dp[v-c];
	}
}

inline int tocent(double x) // 元转换为分
{
	return (int)((x+eps)*100);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%lf%d", &vv, &n), n)
	{
		memset(dp,0,sizeof(dp));
		dp[0] = true;
		V = tocent(vv);
		for (int i = 1,m,sum,a,b,c;i<=n;i++)
		{
			a = b = c = 0; // a、b、c的意思是A、B、C三项报销额度
			scanf("%d", &m);
			sum = 0;
			bool flag = true; // 发票是否合法
			while(m--)
			{
				getchar(); // 吸收多余空格
				char c;
				double kk;
				scanf("%c:%lf", &c,&kk);
				if (!flag) // 已经是无效发票了,但是也要把本张发票的数据读完
				{
					continue;
				}
				int kkk = tocent(kk);
				if (c!='A' && c!='B' && c!='C')
				{
					flag = false;
				}
				else if (c=='A')
				{
					a+=kkk;
					if (a>60000)
					{
						flag = false;
					}
				}
				else if (c=='B')
				{
					b+=kkk;
					if (b>60000)
					{
						flag = false;
					}
				}
				else
				{
					c+=kkk;
					if (c>60000)
					{
						flag = false;
					}
				}
				sum+=kkk;
				if (sum>100000)
				{
					flag = false;
				}
			}
			if (!flag)
			{
				continue;
			}
			zo(sum);
		}
		while(!dp[V])
		{
			--V;
		}
		printf("%.2lf\n", V/100.0);
	}
	return 0;
}

ac情况

Status Accepted
Time 140ms
Memory 4676kB
Length 1439
Lang C++
Submitted 2019-10-27 19:19:32
Shared
RemoteRunId 31138420