蓝桥杯— —小明的背包问题

小明的背包问题

小明的背包1 — — （01背包）

友情链接：小明的背包1

题目：

输入样例:

5 20
1 6
2 5
3 8
5 15
3 3 

输出样例：

37

思路：

对于01背包问题，其中一个重要的条件是每一种物品只有一个，因为在有n个物品v个容量的情况下的最大价值可以由它的子问题n - 1个物品v个容量的最大价值转化而来，因此我们可以利用动态规划的思想进行求解。

我们这样定义dp数组：我们令dp数组的第一维表示每一个物品，dp数组的第二维表示背包的容量。如题目给出的样例，（一共有5个物品，背包的容量为20）我们可以得到如下的dp数组：

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0
1
2
3
4
5

对于第二维（即第一行数字）表示的是背包的容量，对于第一维（即第一列数字）表示的是物品的个数，背包的容量和物品的个数都是隐式存在的，并不是一个值，在程序中体现为下标（或索引）。

初始化dp数组：

对于背包容量为0的情况，我们能放入的物品的个数为0个，因此初始化dp数组的第一列的值为0。对于物品个数为0的情况，能放入背包的物品的个数也为0个，因此我们初始化dp数组的第一行的值为0。

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0
2	0
3	0
4	0
5	0

递推公式：

对于每一行，即每一个物品来讲，如果当前的容量不能放入该物品，那么只能放入前面的物品，即当前容量能放入前面物品的最大价值，公式为：dp[i][j] = dp[i - 1][j]，如果当前的容量能放入该物品，那么就尝试放入该物品，如果放入该物品后的价值更小，就不放入该物品，其值等于没有该物品的情况下当前背包的容量的最大价值，如果放入该物品后价值更大，就放入该物品。对应的公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i] + v[i]])，对于公式dp[i - 1][j - w[i] + v[i]]的理解是，首先每一个物品都是1个，因此要从之前的物品开始减去当前物品的体积（相当于取出一些物品，腾出恰好的空间，得到在背包容量为j - w[i]的情况下的最大价值），然后再放入当前的物品，得到放入当前物品后的价值。公式max(dp[i - 1][j], dp[i - 1][j - w[i] + v[i]])的意义是：对于第i件物品，可以放或者不放，具体取值我哪一种情况的价值更大。

代码：

// 01背包问题
#include<iostream>
#include<vector>
using namespace std;

int solve(){
	int n,v;cin>>n>>v;   // 物品数量和背包容量
	vector<int> value(n + 1, 0);
	vector<int> weight(n + 1, 0); 
	for(int i = 1;i <= n;i ++){
		
		cin>>weight[i];
		cin>>value[i];
	}
	// 进行动态求解
	vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));
	dp[0][0] = 0;
	for(int i = 1;i <= n;i ++){
		dp[i][0] = 0;
	}
	for(int j = 1;j <= v;j ++){
		dp[0][j] = 0;
	}
	// 递推
	for(int i = 1;i <= n;i ++){  // 每一个物品 
		for(int j = 1;j <= v;j ++){  // 背包容量 
			if(j >= weight[i]){
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
			}else{
				dp[i][j] = dp[i - 1][j];   // 不用在和dp[i][j - 1]进行比较了，与完全背包原因一致 
			}
		}
	}
	cout<<dp[n][v]<<endl;
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int t = 1;
	while(t--){
		solve();
	}
	return 0;
}

小明的背包2 — — （完全背包）

友情链接：小明的背包2

题目：

输入样例：

5 20
1 6
2 5
3 8
5 15
3 3 

输出样例：

120

思路：

多重背包问题与01背包问题的区别在于，多重背包的每一种物品都可以有无限多个，因此我们只需要再递推公式上进行略微修改即可。

我们定义一个二维的dp数组，其含义与01背包定义的dp数组一样，第一维表示的是物品的种类，第二维表示的是背包的容量。

对于给出的输入样例，可以建立一下的dp数组。

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0
1
2
3
4
5

定义边界：
背包容量为0和物品种类为0对应的价值都是0，因此我们要将背包容量为0的一列以及物品种类为0的一行初始化为0。

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0
2	0
3	0
4	0
5	0

递推公式：

如果当前的容量不能放下该物品就继承自上一个物品再当前容量的dp值，对应的公式：dp[i][j] = dp[i - 1][j]，可能有些小伙伴会有疑问，为什么不继承为max(dp[i - 1][j], dp[i][j - 1])呢？原因是：对于当前物品而言，如果不能放入，那么前一个容量自然也不能放入，依次类推到容量为0的情况，可以知道从0到当前情况每一个值都继承自当前容量的上一个物品的值，对于上一个物品而言，其值也是随着容量的增加而呈现出非严格单调递增的。所以使用公式：max(dp[i - 1][j], dp[i][j - 1])是没有意义的，当然最后的结果也是正确的，我们没有必要再进行一次额外的判断了。

如果当前的容量能够放下该物品，就对应两种动作：放或不放，如果放的话就在当前容量的基础上减去该物品的体积，然后加上该物品的价值，如果不放就取上一个物品对应当前容量的价值，公式为：dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])，这里与01背包不同的是dp[i][j - w[i]] + v[i]，原因就在于完全背包问题可以对某一种物品放无限次，01背包只能对某一种物品放一次。

代码：

// 完全背包
#include<iostream>
#include<vector>
using namespace std;


int solve(){
	int n,v;cin>>n>>v;
	vector<int> value(n + 1, 0);
	vector<int> weight(n + 1, 0);
	for(int i = 1;i <= n;i ++){
		cin>>weight[i];
		cin>>value[i];
	}
	vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= v;j ++){
			if(j >= weight[i]){
				dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
			}else{
				dp[i][j] = dp[i - 1][j];  // 不用在和 dp[i][j - 1] 进行比较了，因为如果放不下改为物品，那么之前的容量一定是取自上一个物品在当前容量的最大价值 
			}
		}
	}
	cout<<dp[n][v]<<endl;
	
	return 0;
}

int main(){
	ios::sync_with_stdio(0); 
	cin.tie(0);
	int t = 1;
	while(t--){
		solve();
	}
	return 0;
} 

持续更新中…