前言
AcWing算法提高课内容，本文讲解 动态规划
本篇包括以下题目：
⭐️ AcWing 12. 背包问题求具体方案
⭐️ AcWing 9. 分组背包问题
⭐️ AcWing 1013. 机器分配
⭐️ AcWing 734. 能量石
写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来，博主会立即改正！望大家海涵
本文需要先自修基础：背包问题
注：本文中的所有代码全部为优化后的代码，且不提供优化解释，解释请见：背包问题，其中有详细的解释。
背包问题求具体方案
题目要求
题目描述：
输入格式：
输出格式：
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
物品编号范围是 1 … N 。
数据范围：
输入样例：
4 5 1 2 2 4 3 4 4 6
输出样例：
1 4
思路分析
注意，因为要求输出的顺序是按照字典序，故我们在进行dp的过程中，枚举样本需要从大到小枚举，这样我们在按照字典序输出的时候就可以正向循环，查看状态i是由哪个状态j转移而来的 ( j > i )
代码
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for (int i = n; i >= 1; i -- ) for (int j = 0; j <= m; j ++ ) { f[i][j] = f[i + 1][j]; if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]); } int j = m; for (int i = 1; i <= n; i ++ ) if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) { cout << i << ' '; j -= v[i]; } return 0; }
分组背包问题
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，表示最大价值。
数据范围：
输入样例：
3 5 2 1 2 2 4 1 3 4 1 4 5
输出样例：
8
思路分析
裸题，不解释，解释见博客：背包问题
代码
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 110; int v[N][N], w[N][N], s[N]; int f[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { cin >> s[i]; for (int j = 1; j <= s[i]; j ++ ) cin >> v[i][j] >> w[i][j]; } for (int i = 1; i <= n; i ++ ) for (int j = m; j; j -- ) for (int k = 1; k <= s[i]; k ++ ) if (v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); cout << f[m] << endl; return 0; }
