0-1 背包问题

Posted on | In |

题目：

共n个物体，第i个重量为w[i]，价值v[i]，背包最多能背不超过W的物体，求最大的价值

分析：

每个物体只有一个，在容量允许时（W>w[i]），则对于每个物体只有取、不取两种选择

状态：dp[i][j]：前i个物体，在容量为j的时候，最大的价值

状态转移：

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

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
#include<iostream>
#define MAX 100
using namespace std;
int v[MAX],w[MAX];
int c[MAX][MAX];
int x[MAX];
int main(){
	int n,W;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>w[i]>>v[i];
	cout<<"购物车重量"; 
		cin>>W;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=W;j++){//枚举购物车的重量 
			if(j<w[i]){
				c[i][j]=c[i-1][j];
			}
            //购物车的重量大于等于第i件商品的重量 
            //考虑此物品放与不放是否能使当前购物车价值最大
			else{
				c[i][j]=max(c[i-1][j-w[i]]+v[i],c[i-1][j]);		
			}			
		}
	}
	cout<<"最大价值为:"<<c[n][W]<<endl;
	int j=W;
	for(int i=n;i>0;i--){
		//i>0 i=1的时候可能该商品也在背包里 即c[i][j]>0 
	if(c[i][j]>c[i-1][j]){
		x[i]=1;
		j-=w[i];
	}	
		else x[i]=0;
	}
	for(int i=1;i<=n;i++)
	if(x[i]==1) cout<<i<<" ";
	
	
}

image

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
#include<iostream>
#define MAX 100
using namespace std;
int v[MAX],w[MAX];
int dp[MAX];
int main(){
	int n,W;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>w[i]>>v[i];
	cout<<"购物车重量"; 
		cin>>W;
	/*for(int i=1;i<=n;i++){
		for(int j=W;j>0;j--){//枚举购物车的重量 
			if(j>=w[i]){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	
			}
		}
	}*/
    for(int i=1;i<=n;i++){
		for(int j=W;j>=w[i];j--){//枚举购物车的重量 
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	
			
		}
	}
	cout<<"最大价值为:"<<dp[W]<<endl;
}
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
#include<iostream>
#define MAX 100
using namespace std;
int v[MAX],w[MAX];
int dp[MAX];
int main(){
	int n,W;
	cin>>n;

	int sum[n+1];
	sum[0]=0;

	for(int i=1;i<=n;i++)
	cin>>w[i]>>v[i];
	cout<<"购物车重量"; 
		cin>>W;
		//i
	for(int i=1;i<=n;i++)
	sum[i]=sum[i-1]+w[i]; 
	
	for(int i=1;i<=n;i++){
		//剩余容量与w[i]的最大值 
		//sum[i-1]~sum[n]表示 i..n物品重量之和  
		//只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。
		//以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可
			int bound=max(w[i],W-(sum[n]-sum[i-1]));
		for(int j=W;j>=bound;j--){//枚举购物车的重量 
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	
		}
	}
	cout<<"最大价值为:"<<dp[W]<<endl;
}

一个常数优化
前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。

由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的

for i=1..N
for v=V..0
可以改成

for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
这对于V比较大时是有用的。

小结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

参考博客、
http://739789987.blog.51cto.com/8328242/1438296
背包问题9讲
https://www.kancloud.cn/kancloud/pack/70125