目录
- 零. dp 分析
- 一. 分析
- 二. 最初版本的代码
- 三. 优化一维节省空间（执行速度最快）
- 四. 输入时直接计算（执行并不快，但代码量少）
- 五. 区别：一个物品可以选任意多次，因此状态转移不能根据选与不选第i个物品来划分
- 六. 问题：如何找到状态之间的关系，实现状态转移和计算？
零. dp 分析
- 状态表示
- 集合：所有…的集合
- 条件：边界、前几个、后几个、体积小于…、时间小于…等（集合的设计带来的一些边界条件）
- 属性：max、min ......（状态表示了这个集合的什么值？与状态转移相区别）
- 集合：所有…的集合
- 状态计算（状态之间的关系）：主要看最后一步到当前状态的状态转移。
一. 分析
- 状态设计：
f[i][j]: 前 i 个物品，体积为 j，可以取得的最大值 - 状态计算：
f[i][j] = max(f[i][j-vol[i]] + val[i], f[i-1][j]) - 目标状态：
f[number][container]
此题难在状态转移的分析。
- 01背包中：
f[i][j]可以划分为第 i 个物品选还是不选，分别对应之前的两个状态，从而可以转台转移和计算 - 完全背包：假设容积 j 可以容纳至多 k 个第 i 个物品，那么
f[i][j]可以划分为第 i 个物品拿 $[0, k]$ 个，总计 $k + 1$ 个状态，即下方所示。因此理所当然的可以想到对f[i][j]的计算应循环 $k + 1$ 次，那么就是三重循环，当 container = 1000, vol[i] = 1 时，时间复杂度可以达到 $O(10^{9})$ 超时，那么下一步就是想办法优化状态转移。
f[i][j] = max(f[i-1][j-0*vol[i]] + 0*val[i], // 1： 拿 0 个第 i 个物品
f[i-1][j-1*vol[i]] + 1*val[i], // 2： 拿 1 个第 i 个物品
f[i-1][j-2*vol[i]] + 2*val[i], // 3： 拿 2 个第 i 个物品
..., // ...
f[i-1][j-x*vol[i]] + x*val[i], // x+1：拿 x 个第 i 个物品
..., // ...
f[i-1][j-k*vol[i]] + k*val[i]) // k+1：拿 k 个第 i 个物品
一.1. 优化状态转移（y 总）
写出 f[i][j-vol[i]] 和 f[i][j] 的状态转移。
f[i][j] = max(f[i-1][j-0*vol[i]] + 0*val[i], // 1： 拿 0 个第 i 个物品
f[i-1][j-1*vol[i]] + 1*val[i], // 2： 拿 1 个第 i 个物品
f[i-1][j-2*vol[i]] + 2*val[i], // 3： 拿 2 个第 i 个物品
..., // ...
f[i-1][j-x*vol[i]] + x*val[i], // x+1：拿 x 个第 i 个物品
..., // ...
f[i-1][j-k*vol[i]] + k*val[i]) // k+1：拿 k 个第 i 个物品
f[i][j-vol[i]] = max(f[i-1][j-1*vol[i]] + 0*val[i], // 1：拿 0 个第 i 个物品
f[i-1][j-2*vol[i]] + 1*val[i], // 2：拿 1 个第 i 个物品
..., // ...
f[i-1][j-x*vol[i]] + (x-1)*val[i], // x：拿 (x-1) 个第 i 个物品
..., // ...
f[i-1][j-k*vol[i]] + (k-1)*val[i]) // k：拿 (k-1) 个第 i 个物品
由 f[i][j-vol[i]] = max(...)，式子 f[i][j-vol[i]] + val[i] 可以把 val[i] 拿进 max() 里面。
f[i][j-vol[i]] + val[i] = max(f[i-1][j-1*vol[i]] + 0*val[i] + val[i], // 1：拿 0 个第 i 个物品
f[i-1][j-2*vol[i]] + 1*val[i] + val[i], // 2：拿 1 个第 i 个物品
..., // ...
f[i-1][j-x*vol[i]] + (x-1)*val[i] + val[i], // x：拿 (x-1) 个第 i 个物品
..., // ...
f[i-1][j-k*vol[i]] + (k-1)*val[i] + val[i]) // k：拿 (k-1) 个第 i 个物品
合并val[i]的系数
f[i][j-vol[i]] + val[i] = max(f[i-1][j-1*vol[i]] + 1*val[i], // 1：拿 0 个第 i 个物品
f[i-1][j-2*vol[i]] + 2*val[i], // 2：拿 1 个第 i 个物品
..., // ...
f[i-1][j-x*vol[i]] + x*val[i], // x：拿 (x-1) 个第 i 个物品
..., // ...
f[i-1][j-k*vol[i]] + k*val[i]) // k：拿 (k-1) 个第 i 个物品
发现与 f[i][j] 状态转移式子中的第 $[1, k]$ 项相等。
因此在计算 f[i][j] 时，可以使用 f[i][j-vol[i]] + val[i] 表示对应的第 $[1, k]$ 项，故 f[i][j] 的状态转移可以简化为：
f[i][j] = max(f[i-1][j-0*vol[i]] + 0*val[i],
f[i][j-1*vol[i]] + 1*val[i])
即 f[i][j] = max(f[i-1][j], f[i][j-vol[i]] + val[i]) 。
一.2. $k + 1$ 个状态优化总结
- 前一个状态
f[i][j-vol[i]]为什么想到加一个val[i]：因为发现f[i][j-vol[i]]和f[i][j]的很多项系数恰好只差 1，因此尝试加一个。 - 加法拿进函数里，发现状态转移方程中包含了相同的状态。
- 前一个已经计算过的状态
f[i][j-vol[i]]通过加法就包含了f[i][j]的 k 个状态（假设f[i][j]总共 $k + 1$ 个状态） - 综上
f[i][j]转化为了由两个状态计算得来
二. 最初版本的代码
#include<iostream>
#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rep_gt(i, a, b) for(int i = (b); i > (a); -- i)
using namespace std;
const int N = 1e3 + 5;
int f[N][N];
int val[N], vol[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int number = 0, container = 0;
cin >> number >> container;
_rep_le(i, 1, number) {
cin >> vol[i] >> val[i];
}
/**
* @区别：一个物品可以选任意多次，因此状态转移不能根据选与不选第i个物品来划分。
* @问题：如何找到状态之间的关系，实现状态转移和计算？
*
* @状态设计：f[i][j]: 前 i 个物品，体积为 j，可以取得的最大值
* @状态计算：f[i][j] = max(f[i][j-vol[i]] + val[i], f[i-1][j])
* @目标状态：f[number][container]
*/
_rep_le(i, 1, number) {
// first i items
_rep_le(j, 1, container) {
// the containable is j
f[i][j] = f[i-1][j];
if(j >= vol[i]) {
f[i][j] = max(f[i][j-vol[i]] + val[i], f[i][j]);
}
}
}
cout << f[number][container] << endl;
return 0;
}
三. 优化一维节省空间（执行速度最快）
#include<iostream>
#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rep_gt(i, a, b) for(int i = (b); i > (a); -- i)
using namespace std;
const int N = 1e3 + 5;
int f[N];
int val[N], vol[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int number = 0, container = 0;
cin >> number >> container;
_rep_le(i, 1, number) {
cin >> vol[i] >> val[i];
}
_rep_le(i, 1, number) {
// first i items
_rep_le(j, vol[i], container) {
// the containable is j
f[j] = max(f[j-vol[i]] + val[i], f[j]);
}
}
cout << f[container] << endl;
return 0;
}
四. 输入时直接计算（执行并不快，但代码量少）
同 AcWing 2. 【01背包】状态设计-状态计算-代码注意 的最后一步，因为违背了程序局部性原理，因此不是执行速度最快的，但是代码量最少的。
#include<iostream>
#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rep_gt(i, a, b) for(int i = (b); i > (a); -- i)
using namespace std;
const int N = 1e3 + 5;
int f[N];
int val[N], vol[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int number = 0, container = 0;
cin >> number >> container;
_rep_le(i, 1, number) {
cin >> vol[i] >> val[i];
_rep_le(j, vol[i], container) {
// the containable is j
f[j] = max(f[j-vol[i]] + val[i], f[j]);
}
}
cout << f[container] << endl;
return 0;
}
