01背包问题（动态规划）+一维数组的优化_01背包一维数组

01背包问题（动态规划）+一维数组的优化

题目描述：

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 v[i]价，值是 w[i]。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式：

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

4 5
1 2
2 4
3 4
4 5
1
2
3
4
5

输出格式

输出一个整数，表示最大价值。

8
1

数据范围 0<N,V≤1000 0<vi,wi≤1000

这是一道典型的01背包问题。先来说一下01背包和完全背包的区别：01背包的每件物品只能用一次，而升级版的完全背包中的物品可以无限使用。

今天主要来说一下01背包。利用动态规划，其目的就是将原问题分解成几个子问题，通过求解简单的子问题，把原问题给解决，就比如斐波那契数列方程：

f[i]=f[i-1]+f[i-2];

动态规划的核心就是找到原问题与子问题的关系，并列出动态转移方程。

分析：

这里我们可以定义一个二维数组，dp[i][j]表示对于背包容量为j的背包，前i个物品的最优解，即最大价值。
对于一个物品，可以分两种情况：

不选：对于dp[i][j]，不选第i个物品时，dp[i][j]的最优解就是dp[i-1][j]的最优解
选：如果选择，我们就让背包容量减去第i件的物品体积，让dp加上物品价值，即dp[i][j]=dp[i-1][j-v[i]]+w[i];

这样我们就得到了状态转移方程，如果要计算对于前n个物品背包容量为V的背包的最优解，只需要一层一层往前推，通过前面的子问题，求得最终答案。

状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

//遍历各种情况
for(i=1;i<=n;i++){//依次遍历从第1个物品到底n个物品
		for(j=0;j<=v;j++){//依次遍历从0~背包容量v
			//状态转移方程
		}
	}
1
2
3
4
5
6

代码如下：

#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
int v[1010],w[1010];//体积和价值
int main(){
	int n,V;
	int i,j;
	cin>>n>>V;//商品个数和背包容量
	for(i=1;i<=n;i++){
		cin>>v[i]>>w[i];//体积和价值
	}
	for(i=1;i<=n;i++){//依次遍历从第1个物品到底n个物品
		for(j=1;j<=V;j++){//依次遍历从0~背包容量v
			if(j<v[i]){//如果背包容量小于物品体积
				dp[i][j]=dp[i-1][j];//最优解就是上一个物品时的最优解
			}else{//否则就是背包容量大于等于物品体积
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);//拿或者不拿，选最优
			}
		}
	}
	cout<<dp[n][V]<<endl;//输出前n个商品背包为m的最优解
	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

下面我们来优化一下代码。
从空间优化考虑，在上面的二维数组中我们可以发现有很多重复的数据，我们只要得到第i-1层的结果，就能得到答案，对于前面的数据我们完全没必要储存，所以我们可以定义一个一维数组dp[i]表示背包容量为i时的最优解。我们就可以得到一个状态转移方程：

dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

第一个for循环遍历从1~n的物品。第二个for倒序从V到1遍历。这里强调一下，必须是倒序遍历，倒序遍历保证了对于dp[j]，他要调用的dp[j-v[i]]一定是第i-1更新过的，第i层还没有进行更新。这里我们可以用一组数据测试：

以下是测试代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N];
int v[N],w[N];//体积和价值
int main(){
	int n,V;//商品个数和体积
	int i,j;
	cin>>n>>V;//商品个数和背包容量
	for(i=1;i<=n;i++){
		cin>>v[i]>>w[i];//体积和价值
	}
	int num=0;//计数器
	cout<<"逆序遍历输出"<<endl;
	for(i=1;i<=n;i++){//依次遍历从第1个物品到底n个物品
		for(j=V;j>1;j--){
			if(j>=v[i])
				dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
			printf("前%2d个物品背包容量为%2d的最优解：",i,j);
			cout<<dp[j]<<"  ";
			num++;//计数，五个一换行
			if(num%5==0){
				printf("\n");
				num=0;
			}
		}
	}
	cout<<endl<<dp[V]<<endl;//输出背包为V的最优解
	printf("--------------------------------------分割线------------------------------------\n");
	for(i=0;i<N;i++){//初始化
		dp[i]=0;
	}
	num=0;//计数器
		cout<<"正序遍历输出"<<endl;
		for(i=1;i<=n;i++){//依次遍历从第1个物品到底n个物品
			for(j=1;j<=V;j++){//
				if(j>=v[i])
					dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
				printf("前%2d个物品背包容量为%2d的最优解：",i,j);
				cout<<dp[j]<<"  ";
				num++;//计数，五个一换行
				if(num%5==0){
					printf("\n");
					num=0;
				}
			}
		}
		cout<<endl<<dp[V];//输出背包为V的最优解
	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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

优化到这里实际上已经差不多了，实际上我们可以把for循环语句中的if判断直接加到第二个for的终止循环判断上，是完全没有影响的。最终代码如下：
时间复杂度：O(nV),空间复杂：O(N)

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N];
int v[N],w[N];//体积和价值
int main(){
	int n,V;//商品个数和体积
	int i,j;
	cin>>n>>V;//商品个数和背包容量
	for(i=1;i<=n;i++){
		cin>>v[i]>>w[i];//体积和价值
	}
	for(i=1;i<=n;i++){//依次遍历从第1个物品到底n个物品
		for(j=V;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[V]<<endl;//输出背包为V的最优解
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

以下是几道相似题，可以练练手:
01背包模板题
01背包变型
多维条件变量背包