”明月如霜，好风如水，清景无限 “
-
背包问题的经典程度，不言而喻。今天文远就带大家梳理一遍。主要是01背包，完全背包，多重背包和分组背包问题。关于空间压缩可以见：
空间压缩
。 -
关键点：一般用dp[i][j]表示只用前i个物品在背包空间为j的情况下物品的最大价值。
壹
* 01背包
-
描述：n个物品，背包容量m，物品容量v[i]，价值w[i]。物品只能选0次或者1次。
-
状态分析很简单，即
dp[i][j] = max(dp[i-1][j] , dp[i – 1][j – v[i]] + w[i]);
但要注意第i个物品体积v[i]得小于等于j。
-
二维代码
:
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j <= m ; ++j){
dp[i][j] = dp[i - 1][j];
if (j >= v[i]) dp[i][j] = max(dp[i][j] , dp[i - 1][j - v[i]] + w[i]);
}
}
-
一维代码
:分析二维代码发现，如果j正向循环，则dp[i – 1][j – v[i]]会被错误替换为dp[i][j – v[i]]。即dp[j – v[i]]表示的是后者。详细见：
空间压缩
。因此j倒序遍历：
for(int i = 1 ; i <= n ; ++i){
for(int j = m ; j >= v[i] ; --j){
dp[j] = max(dp[j] , dp[j - v[i]] + w[i]);
}
}
贰
* 完全背包
-
描述：n个物品，背包容量m，物品容量v[i]，价值w[i]。物品只能选0次或者无限次。
-
状态分析很简单，即
dp[i][j] = max(dp[i-1][j] , dp[i – 1][j – v[i]] + w[i] , dp[i – 1][j – 2
v[i]] +2 * w[i] , dp[i – 1][j – k * v[i]] + k * w[i]);
但要注意k个i个物品体积k * v[i]得小于等于j。
-
暴力代码
:
for(int i =1 ; i <= n ; ++i){
for(int j = 1 ; j <= m ; ++j){
for(int k = 0 ; k * v[i] <= j ; ++k)
dp[i][j] = max(dp[i][j] , dp[i - 1][j - k * v[i]] + k * w[i]);
}
}
-
二维代码
:发现dp[i][j – v[i]] + w[i] 刚好替换
max(dp[i – 1][j – v[i]] + w[i] , dp[i – 1][j – 2
v[i]] +2 * w[i] , dp[i – 1][j – k * v[i]] + k * w[i]);
同样注意第i个物品体积v[i]得小于等于j。
for(int i =1 ; i <= n ; ++i){
for(int j = 1 ; j <= m ; ++j){
dp[i][j] = dp[i - 1][j];
if(j >= v[i])
dp[i][j] = max(dp[i][j] , dp[i][j - v[i]] + w[i]);
}
}
-
一维代码
:类比上述01背包的等价替换，即状态转移方程正好是i，直接去掉物品维（i），则刚刚好。因为j正向遍历时，i 都是当前物品。
for(int i =1 ; i <= n ; ++i){
for(int j = v[i] ; j <= m ; ++j){
dp[j] = max(dp[j] , dp[j - v[i]] + w[i]);
}
}
叁
* 多重背包
-
描述：n个物品，背包容量m，物品容量v[i]，价值w[i]。物品只能选0次或者最多s[i]个。
-
状态分析：
k = 0 ++ (k <= s[i] && k * v[i] <= m)
dp[i][j] = max(dp[i][j] , dp[i – 1][j – k * v[i]] + k + w[i]);
类比完全背包的暴力做法，但是要加条件k <= s[i]
-
暴力代码
:
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= m ;++j){
for(int k = 0 ; k <= s[i] && j >= k * v[i] ; ++k){
dp[i][j] = max(dp[i][j] ,dp[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
- 降维代码:此处很狗在于，没有完全背包的优化：因为发现dp[i][j – v[i]] + w[i] 不能刚好替换：
*
max(dp[i – 1][j – v[i]] + w[i] , dp[i – 1][j – 2
v[i]] +2 * w[i] , dp[i – 1][j – k * v[i]] + k * w[i]);
多了一个：dp[i -1][j – (s[i] + 1)*v[i] ] + s[i] * w[i]。如下图：
但是我们可以将其转化为01背包问题，即将从0到s遍历换为0到log s。此为二进制优化。其实就是物品打包。
将 n * s的物品变为 n * log s个物品
，物品的v和w都要变化。这是因为 log s 个数二进制能够表示s个数：
-
二进制优化代码
：
///二进制优化,将限制的 s[i] 转换为 log s , 即物品打包，变为 0 1背包
//主要时预处理v和w数组
int idx = 0;
for(int i = 1 ; i <= n ; ++i){
int a , b , s;
scanf("%d%d%d" , &a , &b ,&s);
for(int k = 1; k <= s ; k *= 2){
++idx;
v[idx] = a * k;
w[idx] = b * k;
s -= k;
}
if(s > 0){二进制剩余补全
++idx;
v[idx] = a * s;
w[idx] = b * s;
}
}
n = idx;///即 n 变为了 n * log s
/然后按照 01背包处理
肆
* 分组背包
描述：n组物品，背包容量m，i组第j物品容量v[i][j]，价值w[i][j]。物品只能选0次或者组中1个。
-
关键点：是选i组k个物品中的哪一个，或者i组不选。
-
二维代码
:
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n , m;
int v[N][N] , w[N][N] , s[N];
int dp[N][N];
int main(){
scanf("%d%d" , &n , &m);
for(int i = 1; i <= n ; ++i ){
scanf("%d" , &s[i]);
for(int j = 1 ; j <= s[i] ; ++j)
scanf("%d%d" , &v[i][j] , &w[i][j]);
}
// for(int i = 1 ; i <= n ; ++i){
// for(int j = m ; j > 0 ; --j){注意此处，无法使用 j >= v[i][k]
// for(int k = 1 ; k <= s[i] ; ++k).枚举物品序号????
// if(j >= v[i][k])
// dp[j] = max(dp[j] , dp[j - v[i][k]] + w[i][k]);
// }
// }
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= m ; ++j){注意此处，无法使用 j >= v[i][k]
dp[i][j] = dp[i - 1][j]; /为什么要放在这里呢，即第 i 组不选
for(int k = 1 ; k <= s[i] ; ++k){.枚举物品序号????
//dp[i][j] = dp[i -1][j];
if(j >= v[i][k])
dp[i][j] = max(dp[i][j] , dp[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
printf("%d\n",dp[n][m]);
return 0;
}
for(int i = 1 ; i <= n ; ++i){
for(int j = m ; j > 0 ; --j){注意此处，无法使用 j >= v[i][k]
for(int k = 1 ; k <= s[i] ; ++k).枚举物品序号????
if(j >= v[i][k])
dp[j] = max(dp[j] , dp[j - v[i][k]] + w[i][k]);
}
}
源码可点击
阅读原文
，记得点赞关注。
END
公众号：文远的学习笔记
作者：不爱跑马的影迷不是好程序猿
喜欢的话请关注点赞👇 👇👇 👇
壹句： 他山石