播放CD

问题描述

东东开车出去泡妞(在梦中)，车内提供了 m 张CD唱片，已知东东开车的时间是 n 分钟，他该如何去选择唱片去消磨这无聊的时间呢
假设:
CD数量不超过20张
没有一张CD唱片超过 N 分钟
每张唱片只能听一次
唱片的播放长度为整数
 N 也是整数
我们需要找到最能消磨时间的唱片数量，并按使用顺序输出答案（必须是听完唱片，不能有唱片没听完却到了下车时间的情况发生）

Input

多组输入
每行输入第一个数字N, 代表总时间，第二个数字 M 代表有 M 张唱片，后面紧跟 M 个数字，代表每张唱片的时长。
例如样例一: N=5, M=3, 第一张唱片为 1 分钟, 第二张唱片 3 分钟, 第三张 4 分钟。
所有数据均满足以下条件:
N ≤ 10000
M ≤ 20

Output

输出所有唱片的时长和总时长，具体输出格式见样例

Sample

Input: 
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

Output: 
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

Limitation

Time limit      3000 ms

解题思路

题意就是从 m 个数中选出 k 个( k 不定)，使得这 k 个数的和为 n。这是个0-1背包问题。

用 f_{i, j} 表示考虑前 i 件物品，放入一个容量为 j 的背包可获得的最大价值。

$$f_{i, j} = max(f_{i-1, j}, f_{i-1, j-w_i} + v_i)$$

对于第 i 件物品放或不放，若不放，则变成前 i - 1 件物品放入容量为 j 的背包中；若放，则前 i - 1 件物品放入容量为 j - w_i 的背包中。

本题用 cnt[i][j] 数组标记容量为 j 时，物品 i 取不取，用于输出。

源代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 20000;
const int maxM = 30;

int arr[maxN];
int cnt[maxM][maxN];
int v[maxN];

void solve(int value, int m) {

	for (int i = 0; i < maxN; i++)
		arr[i] = 0;
	
	for (int i = 0; i < maxM; i++)
		for (int j = 0; j < maxN; j++)
			cnt[i][j] = 0;

	for (int i = 1; i <= m; i++) {
		for (int j = value; j >= v[i]; j--) {
			if (arr[j - v[i]] + v[i] > arr[j]) {
				cnt[i][j] = 1;
				arr[j] = arr[j - v[i]] + v[i];
			}
		}
	}
	vector<int> res;
	int j = value;
	for (int i = m; i >= 1; i--) {
		if (cnt[i][j]) {
			res.push_back(v[i]);
			j -= v[i];
		}
	}
	for (int i = res.size() - 1; i >= 0; i--)
		cout << res[i] << " ";
	cout << "sum:" << arr[value] << endl;
}

int main() {
	int n, m;
	while (!(cin >> n >> m).eof()) {
		for (int i = 1; i <= m; i++)
			cin >> v[i];
		solve(n, m);
	}

	return 0;
}