背包问题学习
背包问题是常见的动态规划dp的问题
下面用到的符号:
- 常用n表示物品数, m表示背包容积
f[i][j]表示i件物品, j的背包容量的最大价值- w[i]表示第i件物品的价值, v[i] 表示第i件物品的容量
f[0][0~m] = 0, 所以n可以从1开始遍历- 一般是有两层嵌套循环 第一层遍历物品, 第二层遍历背包容量, 第三层视情况, 若完全背包or多重背包 需要遍历决策 判断 k*v[i] <= j (背包容量)
0/1背包
下图是0/1背包的分析:
题目 (0/1背包)
输入输出
核心代码
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++){ // 不难发现 f[i][] 都是依赖于 f[i-1][] 的
f[i][j] = f[i-1][j];
if(v[i]<=j) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
}
优化: 降维 二维 -> 一维
需要注意的是在遍历背包容量的时候, 需要逆序遍历背包容量, 因为物品只能取一个和不取两种状态, 而逆序能够保证这个。
完整代码如下:
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N]; // 物品体积 价值
int f[N];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i<=n; i++) scanf("%d%d",&v[i],&w[i]);
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]);
}
}
printf("%d\n",f[m]);
return 0;
}
完全背包
下图是完全背包的分析:
题目(完全背包 物品可以无限拿, 只要背包容量还能放得下)
题目和输入/输出
朴素做法(三层循环)
#include<iostream>
#include<algorithm>
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++) scanf("%d%d",&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-k*v[i]]+w[i]*k);
}
}
cout<<f[n][m]<<endl;
return 0;
}
优化:
(通过列举 f[i][j] 以及 f[i][j-v]两种情况, 发现有很多相同之处, 只相差个v) => 化简得
f[i]][j] = max(f[i-1][j], f[i-1][j-v]+w) 两种状态, 一个是取第i件物品, 另一个是不取第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]);
}
}
其实上述代码与0/1背包的代码有很多雷同的地方(都是两种状态, 要么取第i件, 要么不取), 只不过 0/1 背包是 f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]), 而完全背包是 f[i][j] = max(f[i][j], f[i][j-v[i]]+w[i]) (前一部分是不取第i件, 后面是取第i件的方案)
这个状态转移方程的含义可以这样理解：
- 不取第
i件物品：这种情况下，背包的最大价值保持不变，即为f[i][j]。这实际上是上一个状态的值，因为我们没有添加新的物品。 - 取第
i件物品：如果我们决定把第i件物品放入背包中，那么背包的剩余容量变为j-v[i]。因此，当前的总价值是放入这件物品之前的总价值f[i][j-v[i]]加上这件物品的价值w[i]。
对于上面代码的转化:
for(int i = 1; i<=n; i++){
for(int j = v[i]; j <= m; j++){
f[i][j] = max(f[i-1][j], f[i][j-v[i]]+w[i]);
}
}
继续优化:
2维压缩成1维: 这里因为完全背包问题, 物品可以取无数次, 所以第二层循环循环遍历背包容量时, 顺序遍历
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;
多重背包
与上面的背包问题不同的是每个物品数量有上限: 0~s[i]
题目:
状态划分: 两种 -> 取第i件物品 / 不取第i件物品
朴素做法
状态方程:f[i][j] = max(f[i-1][j-k*v[i]]+w[i]*k, f[i][j]), k = 0, 1, 2... s[i]
初级版 多重背包
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n, m;
int s[N], v[N], w[N];
int f[N][N]; // 1~N 个物品, 背包容量为N 所能达到的最大价值 (max)
int main(){
scanf("%d%d", &n,&m);
for(int i = 1; i<=n; i++){ // 输入第i个物品的体积、价值和重量
scanf("%d%d%d",&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-1][j], f[i][j-k*v[i]]+w[i]*k);
}
}
printf("%d\n",f[n][m]);
return 0;
}
当数据量比较大的时候, 上面的代码会出现 TLE, 因此我们需要对上述代码进行优化
优化:
困难版 多重背包
我们可以尝试展开f, 尝试寻找规律
f[i][j] = max(f[i-1][j], f[i-1][j-v]+w,...,f[i-1][j-sv]+sw)
f[i][j-v] = max( f[i-1][j-v], f[i-1][j-2v]+w,...+f[i-1][j-sv]+(s-1)w, f[i-1][j-s+1]v+sw)
但是从上式找不到其中规律,所以下述使用二进制拆解第i个物品个数s[i] 去优化上述代码
2^n的方式进行拆解包-> 01背包问题 s->logs 组, 且每组只能选一次 (拆分)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25000, M = 2010; // 物品数量N NlogS 1000*log2000, 背包体积 M
int n, m;
int v[N], w[N]; // 物体体积, 价值
int f[N]; // dp数组, 这里使用一维数组, 因为物品数量进行重组了
/*
多重背包的优化 (二进制对物品数量进行拆分)
对物品进行拆分, 这样就少了一层循环(第三层k)
*/
int main(){
cin>>n>>m;
int cnt = 0;
for(int i = 1; i <= n; i++){
int a, b, s;
cin>>a>>b>>s; // 输入 第i种物品的体积, 价值
int k = 1;
while(k <= s){ // 拆分次数 s[i]！
cnt++;
v[cnt] = a * k; // k个第i件物品体积 k个 第i件物品体积为a
w[cnt] = b * k; // 更新第i个物品的价值
s -= k;
k *= 2;
}
if(s > 0){ // 剩余的(s个物品)为一件
cnt++;
v[cnt] = a*s;
w[cnt] = b*s;
}
}
n = cnt; // 更新物品数量
// 后继转为 0/1 背包问题, 每个物品 要么拿一次, 要么不拿
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;
}
上述介绍了常见的三种背包问题的思路和基础代码模板以及相应的优化。希望各位大佬能够给予指导以及相应的意见, 后续时间也会取更新更多更丰富的算法内容, 谢谢大家的观看♥~