二维背包
二维背包
二维背包相较于01背包,多了一个限制,就是背包的重量有了限制,但是其本质和01背包并没有什么区别,只是多遍历一轮。
f(i,j,k)状态表示:解锁了前i个物品,背包可以承载体积为j,可以承重为w。
状态转移方程:f(i,j,k)=max( f(i-1,j,k),f(i-1,j-v,k-w)+vi) )
本质和01背包转移方程一致,区分为拿第i种物品,和不拿第i种物品,转移的状态一定是最近的关系,这样才能保证每种状态下都是最优解。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
int n,V,M;
int f[N][110][110];
int main() {
cin>>n>>V>>M;//输入物品个数,背包容积, 可承受最大重量
for(int i=1; i<=n; i++) {
int v,m,w;//每个物品的体积,重量,价值
cin>>v>>m>>w;
for(int j=0; j<=V; j++) {
for(int k=0; k<=M; k++) {
if(j>=v&&k>=m)//背包体积和称重都满足
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-v][k-m]+w);//状态转移方程
else f[i][j][k]=f[i-1][j][k];//不满足时直接继承上一轮结果
}
}
}
cout<<f[n][V][M]<<endl;
return 0;
}
优化为二维
既然01背包都可以优化,那么我们理所应当可以优化二维背包状态数组
由于每次遍历体积和重量时,根据状态转移方程f(i,j,k)=max( f(i-1,j,k),f(i-1,j-v,k-w)+vi) ),每次j和k都需要j-v,和k-w,也就是需要比他们小的状态,并且第i轮只和第i-1轮相关,不受之前影响,那么我们可以把它优化为f(i,j)数组,只需要将体积和重量从后向前遍历,这样每次可以拿到上一轮的j-v和k-w,实质就是打了个时间差。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=110;
int n,V,M;
int f[N][N];
int main() {
cin>>n>>V>>M;//输入物品个数,背包容积, 可承受最大重量
for(int i=0; i<n; i++) {
int v,m,w;//每个物品的体积,重量,价值
cin>>v>>m>>w;
for(int j=V; j>=v; j--) { //体积从后向前(j<=v时自然继承上一轮,也就不用处理)
for(int k=M; k>=m; k--) {
f[j][k]=max(f[j][k],f[j-v][k-m]+w);//状态转移方程
}
}
}
cout<<f[V][M]<<endl;
return 0;
}