题目:
你前面有很长的车程。你有一台录音机,但不幸的是,你最好的音乐是在 CD 上。你需要把它放在磁带上,所以要解决的问题是:你有一个 N 分钟长的磁带。如何从 CD 中选择曲目以充分利用磁带空间并尽可能减少未使用的空间。
假设:
• CD 上的曲目数不超过 20
• 曲目不超过 N 分钟
• 曲目不重复
• 每个音轨的长度以整数表示
• N 也是整数 程序应该找到最能填满磁带的轨道集,并以与轨道存储在 CD 上相同的顺序打印它
输入:
n<=10000,m<=20;
任意数量的行。每一个都包含值 N,(在空格之后)轨道数和轨道持续时间。例如,从样本数据的第一行开始:N = 5,曲目数=3,第一首曲目持续 1 分钟,第二首曲目持续 3 分钟,下一个曲目持续 4 分钟
输出:
一组轨道(和持续时间),它们是正确的解决方案和字符串“sum:”和持续时间的总和。
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
Sample 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
思路分析:
对于sum的求和,从简单的01背包考虑很容易就能得到状态转移方程:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - s[i]] + s[i]);问题在于如何求具体转移的方案,所以我们可以考虑再新建一个数组m记录每次转移所选取的方案,由于我们是顺序记录每次转移的方案,所以我们需要逆序遍历转移的状态才能找到正确的选取的方案。最后我们又需要输出正序的选择的方案,所以我们需要再次逆序输出记录的方案,对此我们可以借助栈的形式,先入栈再出栈就能得到具体的选取方案。对于背包问题具体方案的输出可以参考以下思路。具体解释可见代码注释。
代码:
二维数组的形式:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[25];
int dp[10010][10010];
int m[100][1010];
int main() {
int n, num;
while (~scanf("%d%d", &n, &num)) {
for (int i = 1; i <= num; i++)cin >> s[i];
memset(dp, 0, sizeof(dp));
memset(m, 0, sizeof(m));
for (int i = 1; i <= num; i++) { //个数
for (int j = 0; j <= n; j++) { //空间
if (j - s[i] >= 0) {//如果空间足够选取s[i]取选或不选的最大值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - s[i]] + s[i]);
m[i][j] = 1;//并记录空间为j时的这个状态
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
int v[1100], top = 0;//v为用数组模拟栈,top为栈顶的指针
for (int i = num, j = n; i > 0 && j > 0 ; i--) {//因为dp时是顺序记录的状态,所以我们需要逆序推导一次转移过程
if (m[i][j]) {//如果该状态被记录过
v[++top] = s[i];//将该方案存入栈中
j -= s[i];//空间转移至下一个状态
}
}
while (top) {//所有数据出栈完成逆序输出
cout << v[top--] << ' ';
}
cout << "sum:" << dp[num][n] << endl;
}
return 0;
}
对于dp压维减少空间复杂度的做法:
思路与二维思路一致,因为每次dp[i]的转移都有dp[i-1]有关,所以可以直接压维减少数组维度,但是要注意压维后空间由大到小遍历。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[25];
int dp[100000];
int m[100][10000];
int main() {
int n, num;
while (~scanf("%d%d", &n, &num)) {
for (int i = 1; i <= num; i++)cin >> s[i];
memset(dp, 0, sizeof(dp));
memset(m, 0, sizeof(m));
for (int i = 1; i <= num; i++) {
for (int j = n; j >= s[i]; j--) {
if (dp[j] < dp[j - s[i]] + s[i]) {
dp[j] = dp[j - s[i]] + s[i];
m[i][j] = 1;
} else m[i][j] = 0;
}
}
int v[1100], top = 0;
for (int i = num, j = n; i > 0 && j > 0 ; i--) {
if (m[i][j]) {
v[++top] = s[i];
j -= s[i];
}
}
while (top) {
cout << v[top--] << ' ';
}
printf("sum:%d\n", dp[n]);
}
return 0;
}