二维背包(包含优化)

二维背包

二维背包

二维背包相较于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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

优化为二维

既然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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32