目录
零. dp 分析
- 状态表示
- 集合：所有…的集合
- 条件：边界、前几个、后几个、体积小于…、时间小于…等（集合的设计带来的一些边界条件）
- 属性：max、min ......（状态表示了这个集合的什么值？与状态转移相区别）
- 集合：所有…的集合
- 状态计算（状态之间的关系）：主要看最后一步到当前状态的状态转移。
一. 分析
- 状态设计：
f[i][j]: 前 i 个物品，体积为 j，可以取得的最大值 - 状态计算：
f[i][j] = max(f[i-1][j-k*vol[i]] + k*val[i])，$k \in [0, min(\frac{j}{vol[i]}, num[i])]$ - 目标状态：
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], f[i][j-vol[i]] + val[i])。 - 多重背包：容积 j 可以容纳至多 k 个第 i 个物品，第 i 个物品总共 num[i] 个，综合这两个限制，假设第 i 个物品最多拿
x = min(k, num[i])个。那么f[i][j]可以划分为第 i 个物品拿 $[0, x]$ 个，总计 $x + 1$ 个状态。区别于完全背包，多重背包中，状态f[i][j]和状态f[i][j-vol[i]]之间联系更加复杂，即f[i][j]和f[i][j-vol[i]]可能选用不同的数量来分别得到其最大值，因此之前的优化状态转移不再适用，即要使用完全背包的朴素解法。注意：f[i][j]拿了 x 个第 i 个物品（x 为上述假设的最大数量），f[i][j+1]仍有可能拿 x 个第 i 个物品.f[i][...]含义：要计算拿几个第 i 个物品，可以使从相应的f[i-1][...-(几个*vol[i])]状态转移过来后，可以取得最大值。即，f[i][...]都是从对应方案的f[i-1][...]转移过来的f[i][j]和f[i][j-vol[i]]可能选用不同的数量来分别得到其最大值，因此不能用f[i][j] = max(f[i-1][j], f[i][j-vol[i]] + val[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 个物品
状态转移分析参考： AcWing 3. 完全背包问题 状态转移的分析、优化
二. 最初版本的代码
#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 = 1e2 + 5;
int f[N][N];
int val[N], vol[N], num[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int sum = 0, container = 0;
cin >> sum >> container;
_rep_le(i, 1, sum) {
cin >> vol[i] >> val[i] >> num[i];
}
_rep_le(i, 1, sum) {
// first i items
_rep_le(j, 1, container) {
// container is j
f[i][j] = f[i-1][j];
_rep_le(k, 1, num[i]) {
if(j < k * vol[i]) {
//f[i][j] = max(f[i][j-1], f[i][j]);
// 为什么错请见分析的注意中，第一二点
break;
} else {
f[i][j] = max(f[i-1][j-k*vol[i]] + k*val[i], f[i][j]);
}
}
}
}
cout << f[sum][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 = 1e2 + 5;
int f[N];
int val[N], vol[N], num[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int sum = 0, container = 0;
cin >> sum >> container;
_rep_le(i, 1, sum) {
cin >> vol[i] >> val[i] >> num[i];
}
_rep_le(i, 1, sum) {
// first i items
_rep_ge(j, 1, container) {
// container is j
_rep_le(k, 1, num[i]) {
if(j < k * vol[i]) {
break;
} else {
f[j] = max(f[j-k*vol[i]] + k*val[i], f[j]);
}
}
}
}
cout << f[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 = 1e2 + 5;
int f[N];
int val[N], vol[N], num[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int sum = 0, container = 0;
cin >> sum >> container;
_rep_le(i, 1, sum) {
cin >> vol[i] >> val[i] >> num[i];
_rep_ge(j, 1, container) {
// container is j
_rep_le(k, 1, num[i]) {
if(j < k * vol[i]) {
break;
} else {
f[j] = max(f[j-k*vol[i]] + k*val[i], f[j]);
}
}
}
}
cout << f[container] << endl;
return 0;
}
