求背包容量至少
为j的二维消费0 1背包问题
背包容量可以有三种说法,“最多为j”,“恰好为j”,“至少为j(注意至少为j一般都是求最小值)”
状态表示
f[i][j][k]
表示所有从前i个物品当中选,氧气含量至少
是j
,氮气含量至少是k
的所有选法中气缸重量的最小值
状态计算
按最后一个元素i进行划分:分成选或不选当前元素i
- 不选:
f[i][j][k] = f[i - 1][j][k]
- 选:
f[i][j][k] = max(f[i][j][k],f[i - 1][j - a][k - b]) + c
对于三种不同的背包容量的限制,f[][]
的初始化也不同
1、背包容量最多为j
的初始化【j >= 0】
f[][]
的所有状态都可以初始化为0
因为f[0][i]
表示什么都不选的情况下,总体积是j
的最大价值,那么它的值就为0,那么对于所有f[0][?]
的这种状态都会被包含在f[0][i]
里面,所以所有状态初始化为0
2、背包容量恰好为j
的初始化【j >= 0】
初始化f[0][0] = 0
,其余f[0][j]
初始化为不合法(取"+∞"还是"-∞"取决于当前问题是求最大价值还是最小价值)
因为f[0][j]
表示的是当一个物品都不选的时候,总体积恰好是j
的最大价值,那么这个状态是不合法的,所以在这道题的背景下(取最小值)
取"-∞"
并且计算完最终的状态之后还要枚举最后一层f[n][?]来记录最大(最小值)
3、背包容量至少为j
的初始化(求最小值)【j可以取任意值】
初始化f[0][0] = 0
,其余f[0][j]
也是不合法的初始化为正无穷为了求最小值的时候能够更新每一个状态
,
若j - v1 < 0
,这个状态也是存在的,这个状态f[i][j - v1]
等价于f[i - 1][0]
, 因为背包容量至少为小于0的值的时候也一定包含在背包容量至少为0的状态里面,所以f[i][j - v1]
用f[i][0]
来表示
朴素版
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010,M = 110,INF = 0x3f3f3f3f;
int f[N][M][M];
int t,n,m;
int main(){
cin >> n >> m;
cin >> t;
memset(f,INF,sizeof f);
f[0][0][0] = 0;
for(int i = 1;i <= t;++i){
int a,b,c;
cin >> a >> b >> c;
for(int j = 0;j <= n;++j){
for(int k = 0;k <= m;++k){
f[i][j][k] = f[i - 1][j][k];
//背包容量至少为小于0的值的时候也一定包含在背包容量至少为0的状态里面,
//所以f[i][j - v1]用f[i][0]来表示
f[i][j][k] = min(f[i][j][k],f[i - 1][max(0,j - a)][max(0,k - b)] + c);
}
}
}
cout << f[t][n][m] << endl;
return 0;
}
滚动数组优化版
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010,M = 110,INF = 0x3f3f3f3f;
int f[M][M];
int t,n,m;
int main(){
cin >> n >> m;
cin >> t;
memset(f,INF,sizeof f);
f[0][0] = 0;
for(int i = 1;i <= t;++i){
int a,b,c;
cin >> a >> b >> c;
for(int j = n;j >= 0;--j){
for(int k = m;k >= 0;--k){
//f[j][k] = f[i - 1][j][k];
//背包容量至少为小于0的值的时候也一定包含在背包容量至少为0的状态里面,
//所以f[i][j - v1]用f[i][0]来表示
f[j][k] = min(f[j][k],f[max(0,j - a)][max(0,k - b)] + c);
}
}
}
cout << f[n][m] << endl;
return 0;
}