uva 624 CD 01背包 输出最优方案模板

缘起

【1】中我们给出了背包问题的解，但是没有打印出最优解的方案. 于是找一道题目来打印最优解的方案

遂找到了 uva 624 CD

分析

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
你即将开车出远门，当然希望在车上能聆听一些美好的音乐。你的车上只有播放录音带的设备，
但是你最喜欢的音乐却都存放在CD上。所以你需要把CD上的音乐转录到录音带上。
现在你必须解决的问题是：你的空白录音带长共N分钟，你如何选择CD上的歌使得尽可能的利用录音带的空间。
以下是一些此问题的假设：
CD上的歌最多不会超过20首。
没有任何一首歌的长度超过N分钟。
要录在录音带上的歌不能重复。
每首歌的长度以一整数表达。
N也是一个整数。
你的程式必须找出该放哪些CD上的歌到录音带上（按CD上的顺序），使得录音带空白的空间最小。

【输入】
多样例，每个样例占据一行，首先是N，然后歌的数量，然后是每首歌的时间

【输出】
最优解

【样例输入】
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

【样例输出】
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

显然，必须要在dp的基础上保存达到最优解的选择.

注意，此题dp的时候做了一个改换. 就是dp[i]表示的并不是某某轮中背包容量为i的时候能达到的最大价值（这是经典意义下01背包的意义），这里dp[i]表示某某轮中，背包容量i能不能达到，这是因为本题中物品的价值=费用.所以可以这样优化.

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
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

const int maxn = 10005;
int V,N, a[25],s[25],top; // V是背包容量,N是歌曲的数量, a[i]是第i首歌曲的时长, s[0,...,top)存储最优方案
bool b[25][maxn],dp[maxn]; // b[i][j]（N>=i>=1）表示背包容量为j的时候, 第i首歌曲是否被选择,true表示选择, false表示不选, dp[i]表示背包容量i能否被达到

void zo(int i) // 01背包
{
	for (int v = V; v>=a[i]; v--)
	{
		if (dp[v-a[i]])
		{
			b[i][v] = true; // 在背包容量为v的时候, 第i件物品要选
		}
		dp[v] = dp[v] || dp[v-a[i]];
	}
}

void print()
{
	top=0;
	while(!dp[V])V--; // 最后dp[V]=true, 表示容量V可以达到
	int ans = V;
	while(N)
	{
		if (b[N][V]) // 如果容量为V的时候选择了物品N的话
		{
			V-=a[N];
			s[top++] = a[N]; // 需要用栈存放
		}
		N--;
	}
	while(~(--top))
	{
		printf("%d ", s[top]);		
	}
	printf("sum:%d\n",ans);
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d", &V))
	{
		scanf("%d", &N);
		for (int i = 1; i<=N; i++)
		{
			scanf("%d", a+i);
		}
		memset(dp, 0, sizeof(dp));
		dp[0] = true; // 不选择任何一件物品的时候, 只有容量为0才是可以达到的.
		memset(b, 0, sizeof(b));
		for (int i = 1; i<=N; i++)
		{
			zo(i);
		}
		print();
	}
	return 0;
}

ac情况

Status Accepted
Length 1108
Lang C++11 5.3.0
Submitted 2019-08-19 08:33:56
Shared
RemoteRunId 23786998

参考

【1】https://yfsyfs.github.io/2019/08/18/%E7%99%BE%E7%BB%83oj-2773-%E9%87%87%E8%8D%AF-01%E8%83%8C%E5%8C%85/