有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 v i，价值是 w i
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
- 状态变量
- 确定递推关系(状态转移)
- 确定边界条
1
2
3
|
最大价值是物品数量 i 和 背包容量 j 关系的函数
设函数f[i][j] 表示前面已经装了 i 件物品和放入容量为 j 的背包的最大价值
最终的最大价值就是 i 从0增长到n，j从0增长到m的 f[n][m]
|
确认递推关系
f[i][j] 表示 前面i个物品放入容量j的背包的最大价值
1
2
3
4
5
6
7
8
9
10
11
12
|
如果当前背包容量 j < w[i] 不能放入 那么当前的最大价值 和之前放入 i-1个物品一样，其容量j也不变 f[i][j] = f[i-1][j];
如果当前背包可放入 有两种选择一种是不放入 一种是放入
i = 3 j = 5时 第三件物品不放入时获得价值最大，因为放入之后 j还剩1 是 不能放入其他物品
i = 3 j = 6 , 第三件物品放入时获得价值最大，因为放入之后 j还剩2可装第二件
w v
3 5
2 3
4 6
|
1
2
3
4
5
6
7
8
|
for(int i = 1;i<=n;++i){
for(int j = 1;j<=m;++j){
if(j < w[i]) f[i][j] = f[i-1][j];
else{
f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
}
}
}
|
时间复杂度 空间复杂度o(nm) , o(nm)
滚动数组优化
我们发现 f的i 也就是件数每次只用完上层空间就不用了 其实空间可以优化到o(m)
1
2
3
4
5
6
7
8
|
for(int i = 1;i<=n;++i){
for(int j = 1;j<=m;++j){
if(j < w[i]) f[j] = f[j];
else{
f[j] = max(f[j],f[j-w[i]]+v[i]);
}
}
}
|
其实这样还是有问题 因为我们在计算一个f[j]的值 实际上是依赖以前旧的时候计算的值. 而这时候你如果遍历到后面 用到了f[j-w[i]]的值的时候 有可能那个位置是刚刚更新过的 而实际上你要用旧的值来计算
j是顺序循环，f[j-w[j]]是会优先于f[j]更新，也就是说 用新值f[j-w[j]]去更新f[j] 错误
如果j为逆序循环 f[j]就会优于f[j-w[j]]的值 也就是用旧值去更新f[j] , 相当于用上一行的旧值更新 所以正确
因为逆序所用的值是前面的 而用完 刚好这个点计算完了 可以覆盖 【以后也不会再用到】
1
2
3
4
5
6
7
8
9
|
for(int i = 1;i<=n;++i){
for(int j = m;j>=1;++j){ //j
//if(j < w[i]) f[j] = f[j]; 可以不用要
//else{
if(j >= w[i])
f[j] = max(f[j],f[j-w[i]]+v[i]);
//}
}
}
|
习题
https://www.luogu.com.cn/problem/P1048