Week11_T6
题目描述
东东开车出去泡妞(在梦中)，车内提供了 n 张CD唱片，已知东东开车的时间是 n 分钟，他该如何去选择唱片去消磨这无聊的时间呢？
假设:
- CD数量不超过20张
- 没有一张CD唱片超过 N 分钟
- 每张唱片只能听一次
- 唱片的播放长度为整数
- N 也是整数
我们需要找到最能消磨时间的唱片数量，并按使用顺序输出答案（必须是听完唱片，不能有唱片没听完却到了下车时间的情况发生）
本题是 Special Judge。
输入格式
多组输入
每行输入第一个数字N, 代表总时间，第二个数字 M 代表有 M 张唱片，后面紧跟 M 个数字，代表每张唱片的时长 例如样例一: N=5, M=3, 第一张唱片为 1 分钟, 第二张唱片 3 分钟, 第三张 4 分钟
所有数据均满足以下条件:
N≤10000
M≤20
输出格式
输出所有唱片的时长和总时长，具体输出格式见样例。
样例输入
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
解题思路
这道题就是01背包问题，不过，额外的，我们需要得到具体都往背包里塞了哪些东西（选了哪些CD唱片）
在执行01背包的算法的过程中，我们额外开一个choose数组记录某个物品在某个容量下是否被取了。
由于输出要求正序而我的程序是使用了逆序枚举背包的容量，所以使用了栈结构储存答案。
在处理刚才得到的choose数组时，初始分析choose[m][n]，对于某个choose[i][j]，如果等于1，说明被选取了，将其泵入栈中，然后当前分析的背包容量j减去这个被选的物品的重量a[i]。如此循环，直到i和j中任意一个不大于0为止。
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;int a[10005];
int f[25][10005];
int chosen[25][10005];int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;//总时间int m;//CD数量while (cin >> n){cin >> m;for (int i = 1; i <= m; i++){cin >> a[i];}for (int i = 0; i <= n; i++) f[0][i] = 0;for(int i=1;i<=m;i++)for (int j = n; j >= 0; j--){f[i][j] = f[i - 1][j];chosen[i][j] = 0;if (j - a[i] >= 0 && f[i - 1][j - a[i]] + a[i] > f[i][j]){f[i][j] = f[i - 1][j - a[i]] + a[i];chosen[i][j] = 1;}}int i = m;int j = n;stack<int>list;while (i > 0 && j > 0){if (chosen[i][j] == 1){list.push(a[i]);j -= a[i];}i--;}while (!list.empty()){cout << list.top() << ' ';list.pop();}cout << "sum:" << f[m][n] << endl;}
}
Week11_T6
题目描述
东东开车出去泡妞(在梦中)，车内提供了 n 张CD唱片，已知东东开车的时间是 n 分钟，他该如何去选择唱片去消磨这无聊的时间呢？
假设:
- CD数量不超过20张
- 没有一张CD唱片超过 N 分钟
- 每张唱片只能听一次
- 唱片的播放长度为整数
- N 也是整数
我们需要找到最能消磨时间的唱片数量，并按使用顺序输出答案（必须是听完唱片，不能有唱片没听完却到了下车时间的情况发生）
本题是 Special Judge。
输入格式
多组输入
每行输入第一个数字N, 代表总时间，第二个数字 M 代表有 M 张唱片，后面紧跟 M 个数字，代表每张唱片的时长 例如样例一: N=5, M=3, 第一张唱片为 1 分钟, 第二张唱片 3 分钟, 第三张 4 分钟
所有数据均满足以下条件:
N≤10000
M≤20
输出格式
输出所有唱片的时长和总时长，具体输出格式见样例。
样例输入
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
解题思路
这道题就是01背包问题，不过，额外的，我们需要得到具体都往背包里塞了哪些东西（选了哪些CD唱片）
在执行01背包的算法的过程中，我们额外开一个choose数组记录某个物品在某个容量下是否被取了。
由于输出要求正序而我的程序是使用了逆序枚举背包的容量，所以使用了栈结构储存答案。
在处理刚才得到的choose数组时，初始分析choose[m][n]，对于某个choose[i][j]，如果等于1，说明被选取了，将其泵入栈中，然后当前分析的背包容量j减去这个被选的物品的重量a[i]。如此循环，直到i和j中任意一个不大于0为止。
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;int a[10005];
int f[25][10005];
int chosen[25][10005];int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;//总时间int m;//CD数量while (cin >> n){cin >> m;for (int i = 1; i <= m; i++){cin >> a[i];}for (int i = 0; i <= n; i++) f[0][i] = 0;for(int i=1;i<=m;i++)for (int j = n; j >= 0; j--){f[i][j] = f[i - 1][j];chosen[i][j] = 0;if (j - a[i] >= 0 && f[i - 1][j - a[i]] + a[i] > f[i][j]){f[i][j] = f[i - 1][j - a[i]] + a[i];chosen[i][j] = 1;}}int i = m;int j = n;stack<int>list;while (i > 0 && j > 0){if (chosen[i][j] == 1){list.push(a[i]);j -= a[i];}i--;}while (!list.empty()){cout << list.top() << ' ';list.pop();}cout << "sum:" << f[m][n] << endl;}
}
发布评论