01背包
- 01背包每种物品只有1件
- 你要吗装,要么不装
理解
- 装:1
- 不装:0
算法流程
数组定义:
dp[i][j] : 前i钟物品在背包容量为j时装的最大价值
转移方程:
对于第i件物品有两种情况: vi表示第i件物品的体积或重量,wi表示价值 情况1:背包容量足够大j >= vi,可以装第i件物品: 装:dp[i][j] = dp[i - 1][j - vi] + wi; 不装:dp[i][j] = dp[i - 1][j]; 故:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vi] + wi); 情况2:背包容量不够大 j < vi,装不了:dp[i][j] = dp[i - 1][j];
初始化:
memset(dp, 0, sizeof(dp));
代码演示朴素版
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (j >= v[i]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
代码演示二:空间优化
思路:由0-1背包的状态转移方程dp[i] [j] = max{dp[i - 1] [j],dp[i - 1] [j-v[i] ]+w[i]}
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
的特点,知道当前状态仅依赖前一状态的剩余容量与当前物品重量v[i]的关系。
根据这个特点,我们可以将dp降到一维即dp[j] = max{dp[j],dp[j-w[i]]+v[i]}。从这个方程中我们可以发现,有两个dp[j],但是要区分开。
等号左边的j是当前i的状态,右边括号中的j是第i-1状态下的值。
保证
dp[j - vi]
未在此轮计算过, 即dp[j - vi]
依然属于i-1
行如果j从0到V遍历,那么更新到 j 时,dp[j - vi]已经更新过了,变为第i行的dp[j - vi],不再是第i - 1行的 dp[j - vi]
for (int i = 1; i <= n; i++) {
for (int j = V; j >= 1; j--) {
if (j >= v[i]) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
解释:V为背包最大(容量或体积或承重量),dp[j] 表示背包容量为j时的最大价值
完全背包
- 每种物品数量没有限制
- 一种物品你可以重复装,无限制
算法流程
数组定义:
dp[i][j] : 前i钟物品在背包容量为j时装的最大价值
转移方程:
对于第i件物品有两种情况: vi表示第i件物品的体积或重量,wi表示价值 情况1:背包容量足够大j >= vi,可以装第i件物品: 装:dp[i][j] = dp[i - 1][j - vi] + wi; 不装:dp[i][j] = dp[i - 1][j]; 故:dp[i][j] = max(dp[i - 1][j], dp[i][j - vi] + wi); 情况2:背包容量不够大 j < vi,装不了:dp[i][j] = dp[i - 1][j];
初始化:
memset(dp, 0, sizeof(dp));
重点
对于前i种物品,我们可以装多件该物品,则转移方程为:
dp[i][j] = max(dp[i - 1][j], dp[i][j - vi] + wi);
代码实现
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (j >= v[i]) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
} else dp[i][j] = dp[i - 1][j];
}
}
空间优化
- 对当前dp[i] [j],只与当前行也就是dp[i] [j - vi](加)和dp[i - 1] [j](不加)有关
- 故需要知道dp[i] [j - vi],则j从0到V
代码演示
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (j >= v[i]) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
多重背包
- 每种物品数量有限制
- 一种物品i你可以重复装,至多可以装si件
- 多重背包是介于01背包和完全背包之间,更贴切现实生活
转化
多重背包转化为01背包
代码演示
#define MAX_V 100005
int dp[MAX_V];
int v[101], s[101], w[101];
int V, n;
void duochongbeibao() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s[i]; j++) { //当成01背包,相同物品当作不同物品循环
for (int vv = V; vv; vv--) {
if (vv >= j * v[i]) {
dp[vv] = max(dp[vv], dp[vv - v[i]] + w[i]);
}
}
}
}
printf("%d\n", dp[V]);
return ;
}
速度太慢了
二进制拆分优化
对于上面代码,我们是循环遍历每个si,效率太慢
例如对于si = 71
那么si = 1 + 2 + 4 + 8 + 16 + 32 + 8
代码演示
for (int i = 1; i <= n; i++) {
for (int k = 1; s[i]; s[i] -= k, k <<= 1) { //当成01背包,相同物品当作不同物品循环
k = min(k, s[i]);
//printf("%d %d\n", k, s[i]);
for (int j = V; j >= k * v[i]; j--) {
dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
空间优化
for (int i = 1; i <= n; i++) {
int s, w, v;
scanf("%d %d %d", &s, &v, &w);
for (int k = 1; s; s -= k, k <<= 1) { //当成01背包,二进制拆分
k = min(k, s);
//printf("%d %d\n", k, s);
for (int j = V; j >= k * v; j--) {
dp[j] = max(dp[j], dp[j - k * v] + k * w);
}
}
}
单调队列优化
- 最快的多重背包做法
时间复杂度:O(nV)