前言
动态规划一般可以从两个方面表示：
- 状态表示，需要几维表示问题，如01背包需要两维度
f(i,j) - 状态表示的集合是什么
- 这个集合的属性：集合的最大值、最小值、元素的数量。。。
- 状态转移：对应集合划分
背包问题
1 01 背包
1.1 题目
有n件物品和一个容量为v的背包，第i件物品价值为w[i]，求解将哪些物品装入背包可使总价值最大。
1.2 朴素分析
01背包的特点：每个物品仅有一件，可以放或不放。
-
状态表示：
f[i][j]表示前i件装入容量为j的背包可以获得最大价值 -
状态转移方程：是否选择第
i件物品
f[i][j] = max{f[i-1][j],f[i-1][j-v[i]] + w[i]]}
代码：
#include <iostream>
using namespace std;
const int N = 1010;g
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; 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]);
}
}
cout << f[n][m] << endl;
return 0;
}
1.3 优化
朴素方法时间和空间复杂度均为O(VN)，其中时间复杂度应该不能优化了，但空间复杂度可以优化到O(N)。
朴素方法中存在一个for循环for(int i = 1; i <= n; i ++)使得每次可以求出f[i][0...j]的值。
我们的目标时通过一维数组f[j]保证第i次循环后f[j]表示的是我们定义的f[i][j]。
因为f[i][j]=max(f[i-1][j], f[i-1][j-v[i]]+w[i])，这要求保证在推f[i][j]（即第i次for循环推f[j]）时能够取用f[i-1][j]和f[i-1][j-v[i]]的值。
这要求，每次主循环中通过for(j=m;j >= v[i]; j--)递减的顺序计算f[j]，这样才能保证计算f[j]时f[j-v[i]]保存的是状态f[i-1][j-v[i]]的值。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++) {
for (int j >= m; j >= 0; j --) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
1.4 初始化的细节
对于类背包问题，通常有两种文法：
- 装满背包时的最优解
- 不需要装满背包时的最优解
对于问题一，初始化为：
f[0] = 0;
for (int i = 1; i <= n; i ++) f[i] = -3f3f3f3f; // 相当于-∞
对于问题二，初始化为：
for (int i = 0; i <= n; i ++) f[i] = 0;
可以理解为：
初始化的 f 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什 么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于 未定义的状态，应该被赋值为
-∞了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。
2 完全背包
2.1 题目
有n个物品和一个容量为v的背包，每种背包都有无限件可用。放入第i种物品的体积是v[i]，价值是w[i]。求解：将哪些物品装入背包，使总价值最大。
2.2 朴素分析
完全背包的特点：每个物品有无限件，可以取0件、1件、2件…k件
-
状态表示：
f[i][j]表示前i件物品装入容量为j的背包可以获得的最大价值 -
状态转移方程：第
i件物品可以选择多少件
f[i][j]=max{f[i-1][j-k*v[i]]+k*w[i]} 0<=k*v[i]<=j
代码：
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
for (int k = 0; k * v[i] <= j; k ++) {
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}
}
}
cout << f[n][m] << endl;
return 0;
}
2.3 优化
可以观察到：
f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2]+2w, ...)
f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v]+w,...)
因此，有：
f[i][j]=max(f[i-1][j],f[i][j-v]+w)
代码：
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; 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][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
对于f[i][j]=max(f[i-1][j],f[i][j-v[i]] + w[i])，可以通过一维数组实现f[j] = max(f[j],f[j - v[i]] + w[i])
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++) {
for (int j = v[i]; j <= m; j ++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
3 多重背包
3.1 题目
有n种物品和一个容量为v的背包，第i个物品有s[i]件可用，价值为w[i]，使得背包总价值最多。
3.2 朴素分析
多重背包特点：每个物品有s[i]个
- 状态表示：
f[i][j]从前i个物品选，总体积不超过j的总价值最大的选法 - 状态转移：
f[i][j] = max(f[i-1][j-v[i]*k]+w[i]*k) k = 0,1,2,...s[i]&&k*v[i]<=j
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ ) {
f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
3.3 优化
转换成01背包问题。把第i件物品换成m件01背包种的物品。
- 例如把s[i]=1024，打包成1，2，4，8，…，512件01背包物品的组合
- 对于任意的
0~s的取法，可以由2^0,2^1,...2^{k},c的组合得到，其中c<2^{k+1}
#include <iostream>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N];
int f[M];
int main()
{
cin >> n >> m;
// 01背包化：二进制法
int cnt = 0;
for (int i = 1; i <= n; i ++ ) {
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while (k <= s) {
cnt ++ ;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0) {
cnt ++ ;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
// 01背包问题的解
n = cnt;
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
4 分组背包问题
4.1 题目
有n组物品，每组物品最多选一件，每件物品体积v[i][j]，价值w[i][j]（i是组号，j是组内物品编号）
4.2 分析
- 状态表示：
f[i][j]从前i组物品选择，体积不超过j的价值最大的选法 - 状态转移方程：
f[i][j] = max(f[i-1][j], f[i-1][j-v[i,k]] + w[i,k])
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main() {
cin >> n >> m; // 组数，背包容量
for (int i = 1; i <= n; i ++) {
cin >> s[i]; // 组内物品数
for (int j = 0; j < s[i]; j ++) {
cin >> v[i][j] >> w[i][j];
}
}
for (int i = 1; i <= n; i ++) {
for (int j = m; j >= 0; j --) {
for (int k = 0; 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;
}
