2017百度之星资格赛 hdu6083 度度熊的午饭时光 01背包输出字典序最小解

缘起

学习01背包问题输出字典序最小解~ 2017百度之星资格赛 hdu6083 度度熊的午饭时光

分析

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
度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。

百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。

但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)
Input
第一行一个整数T，表示T组数据。
每组测试数据将以如下格式从标准输入读入：

B

N

score_1 cost_1

score_2 cost_2

:

score_N cost_N
  
第一行，正整数B（0 <= B <= 1000），代表午餐的预算。

第二行，正整数N (0 <= N <= 100)，代表午餐可选的菜品数量

从第三行到第 (N + 2) 行，每行两个正整数，以空格分隔，score_i表示菜品的得分，cost_i表示菜品的价格(0 <= score_i, cost_i <= 100)。
Output
对于每组数据，输出两行：
第一行输出："Case #i:"。i代表第i组测试数据。
第二行输出菜品的总得分和总花费，以空格分隔。
第三行输出所选菜品的序号，菜品序号从1开始，以空格分隔。
Sample Input
2
29
6
9 10
3 4
6 5
7 20
10 9
15 11
0
2
2 23
10 12
Sample Output
Case #1:
34 29
2 3 5 6
Case #2:
0 0

【1】中考虑了01背包的最优解方案的输出. 本题进一步加强为01背包问题的字典序最小的最优解方案.

关于字典序最小的01背包方案的求解在《背包九讲2.0》的9.2已经论述过了.

这里再讲一遍. 对于一般的01背包问题, 它考虑的问题是前缀物品（即物品[1,..,i]）的01背包问题的解.

则[1,..,i]问题的解可以根据物品i选与不选, 转换为[1,…,i-1]物品的解（注意，这里没有把容量限制写上, 但是心里明白就好, 不多说）. 这就是一般01背包的问题的dp解法. 而对于字典序最小的01背包问题. 我们要转换dp的对象, 即考虑的是后缀问题的解. 即物品[n-i+1,…,n]的选取（1<=i<=n）. 即令

dp[n-i+1]是考虑物品 [n-i+1,..,n]的选取的时候, 字典序最小的最优解. 则考虑dp[n-i], 即考虑物品[n-i,…,n]的选取的时候, 字典序最小的最优解. 而这根据物品n-i选与不选来分类讨论, 如果选取物品n-i的话, 则显然我们就归于子问题[n-i+1,…,n], 如果不选的话, 也是归于子问题[n-i+1,…,n], 所以我们明白了解决01背包字典序最小解的问题的关键是将物品的存还是取的考虑顺序倒过来，即先考虑第n件物品的存取，然后是第n-1件物品,…,最后是第一件物品, 自然的， 虽然我们dp问题的意义变了, 但是写起来是没有变化的. 而且如果我们考虑的子问题是[1,…,i]的话, 即我们考虑的是[1,..,i]字典序最小这个问题的话, 则你就无法像[n-i+1,…,n]一样推导. 因为选择i和不选i得到的都未必是[1,..,i-1]字典序最小的子问题.

具体实现01背包字典序最小可以参见【2】, 但是我觉得它打印解的做法是错的.

我根据上面的思想, 很快

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
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#define LOCAL
const int maxn = 105, maxv = 1005;
int b,n,score[maxn], cost[maxn], dp[maxv], kk[maxn][maxv],ans[maxn], top; // ans+top描述了最后要打印的解

void zo(int i, int w, int c)
{
	for (int v = b; v>=c; v--)
	{
		if (dp[v]<=dp[v-c]+w) // 注意, 对于输出01背包任意最优解方案的问题,这里可以写<,也可以写<=,但是对于求字典序最小的方案的话, 则必须<=, 因为我们希望尽可能的选物品i（因为这里i是倒序的, i在不断变大就意味着i对应的实际序是在不断变小,字典序就在变大）
		{
			kk[i][v] = 1; // 考虑物品[1,..,i]（注意,物品已经倒序了,其实就是原先的物品[n-i+1,...,n]）,容量为v的时候选择物品i（即原先的物品n-i+1）
			dp[v] = dp[v-c]+w;
		}
	}
}

void printsol() // 这里打印01背包解的算法和《背包九讲2.0》9.1节一样, 因为9.2说了,字典序最小和普通的01背包打印最优解就是倒序这一点不同,其他都一样
{
	if (!dp[b])
	{
		puts("0  0");
		return;
	}
	int totcost = 0; // 总耗费
	for (int i = n,v = b;i;i--) // 从最大的dp子问题开始考察起, 其实就是按照原先的序开始考察
	{ // 这个for可以看做是01背包打印解的模板
		if (kk[i][v]) // [1,...i]容量为v时选了物品i
		{
			totcost+=cost[i];  // 这里还是i,表示选择了物品i(即原先的物品n-i+1) 这里统计总耗费
			ans[top++] = n-i+1; // 最后要还原回来, 即物品i实际上是原先物品的n-i+1
			v-=cost[i];
		}
	}
	printf("%d %d\n", dp[b], totcost);
	for (int i = 0;i<top;i++)
	{
		if (i)
		{
			putchar(' ');
		}
		printf("%d", ans[i]);
	}
	puts("");
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for(int kse  =1;kse<=kase; kse++)
	{
		printf("Case #%d:\n", kse);
		scanf("%d%d", &b, &n);
		memset(kk,0,sizeof(kk));
		memset(dp,0, sizeof(dp));
		top = 0;
		for (int i = n;i;i--) // 这是字典序最小的关键——逆序输入物品, 即(score[n],cost[n])其实是第一件商品,(score[1],cost[1])实际上是最后一件商品
		{
			scanf("%d%d", score+i, cost+i);
		}
		for (int i = 1;i<=n;i++)
		{
			zo(i, score[i], cost[i]);
		}
		printsol(); // 打印字典序最小的最优解
	}
	return 0;
}

但是代码很快被wa掉了. 后来对拍发现, 我的代码的确是打印了字典序最小解. 但是没有考虑到题目要求的”序号和最小”, 即题目要求输出的背包解有三个关键字

  1. 第一关键字是背包的值, 降序排序
  2. 第二关键字是序号和, 升序排序
  3. 第三关键字是字典序, 升序排序

上面wa掉的代码仅仅考虑了第一和第三关键字, 能不错吗? 那么怎么考虑第二关键字呢? 就是在zo的时候, 不能仅仅考虑dp[v]和dp[v-c]+w之间的大小关系. 我们还需要维护一个sum数组, 其中 sum[i][v] 表示前i项（考虑到字典序,其实是后缀i项 [n-i+1,…,n]）容量为v时取得最大背包值时的最小序号和. 则sum的初始化如下

1
2
3
sum[0][0,...,v] = 0, 不取任何物品, 容量限制随意, 自然序号和为0
sum[0,...,n][0] = 0, 限定容量为0, 则自然你一件物品都选不了, 自然序号和为0
sum[others][others] = inf. 因为是求最小嘛~ 而且others情况下的最大背包容量都没确定.

然后zo的时候, 到底选不选第i件物品（即原本的n-i+1件物品）就要考虑sum的因素了

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int maxn = 105, maxv = 1005, inf = 0x3f3f3f3f;
int b,n,score[maxn], cost[maxn], dp[maxv], kk[maxn][maxv],ans[maxn], top, sum[maxn][maxv]; // sum定义见文章

void zo(int i, int w, int c)
{
	for (int v = b; ~v; v--)
	{
		sum[i][v] = sum[i-1][v]; // 默认不选i号物品(即原本的n-i+1号物品)
		if (v<c) // 对于v<c的sum也是需要维护的(如果不去维护, 就是inf, 但是根据sum的定义, 最后其实所有的sum都不应该是inf,因为总有最大背包值的,所以总有对应的sum)
		{
			continue;
		}
		if (dp[v]<dp[v-c]+w) // 第一关键字, 没什么好讲的,肯定要选i号物品(即原本的n-i+1号物品)
		{
			dp[v] = dp[v-c]+w;
			sum[i][v] = sum[i-1][v-c]+n-i+1;
			kk[i][v] = 1;
		}
		else if (dp[v]==dp[v-c]+w) // 第一关键字相同
		{
			if (sum[i][v] >= sum[i-1][v-c]+n-i+1) // 如果选i号物品(即原本的n-i+1号物品)使得第二关键字不大于不选的情况, 就要选i号物品(即原本的n-i+1号物品), 之所以是>= 是因为考虑到字典序, 我们应该尽量去选i
			{
				sum[i][v] = sum[i-1][v-c]+n-i+1;
				kk[i][v] = 1;
			}
		}
	}
}

void printsol()
{
	if (!dp[b])
	{
		puts("0 0");
		return;
	}
	int totcost = 0;
	for (int i = n,v = b;i;i--)
	{
		if (kk[i][v])
		{
			totcost+=cost[i];  
			ans[top++] = n-i+1;
			v-=cost[i];
		}
	}
	printf("%d %d\n", dp[b], totcost);
	for (int i = 0;i<top;i++)
	{
		if (i)
		{
			putchar(' ');
		}
		printf("%d", ans[i]);
	}
	puts("");
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for(int kse  =1;kse<=kase; kse++)
	{
		printf("Case #%d:\n", kse);
		scanf("%d%d", &b, &n);
		memset(kk,0,sizeof(kk));
		memset(dp,0, sizeof(dp));
		memset(sum, 0x3f, sizeof(sum));
		for (int i = 0;i<=n; i++)
		{
			sum[i][0] = 0;
		}
		for (int i = 0;i<=b;i++)
		{
			sum[0][i] = 0;
		} // 初始化sum
		top = 0;
		for (int i = n;i;i--)
		{
			scanf("%d%d", score+i, cost+i);
		}
		for (int i = 1;i<=n;i++)
		{
			zo(i, score[i], cost[i]);
		}
		printsol();
	}
	return 0;
}

ac情况

Status Accepted
Time 15ms
Memory 2568kB
Length 1768
Lang C++
Submitted 2019-10-26 16:01:45
Shared
RemoteRunId 31115362

所以不难看出, 对于背包问题, 死套模板是没有出路的, 本题并不是一个单纯的输出字典序最小解的01背包问题, 百度在设计比赛题目的时候还是做了相应变化的.

看了网上很多题解, 好像都只是说 01背包打印路径~ 并没有考虑到序列号之和最小, 但是也都A了, 不晓得是不是数据较弱还是其他什么原因导致的.

参考

【1】https://yfsyfs.github.io/2019/08/19/uva-624-CD-01%E8%83%8C%E5%8C%85-%E8%BE%93%E5%87%BA%E6%9C%80%E4%BC%98%E6%96%B9%E6%A1%88%E6%A8%A1%E6%9D%BF/

【2】https://blog.csdn.net/qq415200973/article/details/9321609