前言
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; }