赞
踩
最近专注于写了一些关于01背包的问题,总结了些规律和心得,分享一下
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
题目如下:
小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间,并且具有不同的价值。
小明的行李空间为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料只能选择一次,并且只有选与不选两种选择,不能进行切割。
力扣中没有01问题的母体,可以去46. 携带研究材料(第六期模拟笔试) (kamacoder.com)卡码网上联系。
对于简单的背包问题可以使用暴力破解,对于每个物品我们有两种选择:取于不取,可以利用回溯取到所有可能的情况,时间复杂度为O(2^n),复杂度是指数级别的,所以我们可以用动态规划来降低复杂度。
对于动态规划问题,我们采取五部曲策略:
1、确认dp数组以及下标的含义
2、确定递推公式
3、dp数组初始化
4、确定遍历顺序
5、举例推导dp数组
上面五步都很重要,每一步出现错误都会造成很严重的错误,在后面的例题中会逐一说明其重要性。
对于01背包问题,我们采取五步走
1、确认dp数组以及下标的含义
采用二维数组dp[i][j],表示从0-i件商品中任意挑选装入容量为j的背包中,可以得到的最大价值。dp数组的定义十分重要,后面的解题思路都是根据dp数组的定义走的,要是代码写到后面弄混了就回过头来看下定义。
2、确定递推公式
对于dp[i][j]我们有两种选择:取或不取物品i,所以可以从两个方向推导到dp[i][j]
不取物品i:
不取物品i,价值就不变,即dp[i][j]=dp[i-1][j]
取物品i:
决定要取该商品,则相当于将背包容量为j的背包空出weight[i]的重量来放物品i,价值就相当于dp[i-1][j-weight[i]]+values[i],则递推式为dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])
3、dp数组初始化
由上面的递推式我们要用到i-1,所以对于dp[0][j],dp[i][0]我们要进行初始化,对于后者,我们直到其含义为将0-i件物品放入容量为0的背包的价值最大值,很显然都放不进去,所以dp[i][0]=0。对于dp[0][j],我们要关注第一件商品的质量是否超过了背包容量,若没超过,即weight[0]<w,dp[0][j]=values[0],若超过了,dp[0][j]=0。我们在初始化dp数组时就可以将其都初始化为0,因为价值不会出现负值,我们就只需要对dp[0][j]进行考虑了。
4、确定遍历顺序
对于遍历顺序,先遍历物品还是先遍历背包都可以,因为dp[i][j]是通过上一状态来的,最后都能正确的更新最后的值。但对于很多其它问题,遍历顺序的不同就会影响结果,比如完全背包问题还有利用滚动数组优化本题,总的来说,对于遍历顺序,要考虑随着遍历进行,每个值是否会被准确的更新,是否只跟前一个数据有关。对于绝大多数问题,先遍历物品再遍历背包既好理解又正确。
这里采取先遍历物品再遍历背包:
- for(int i = 1; i < weight.size(); i++) { // 遍历物品
- for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
- if (j < weight[i]) dp[i][j] = dp[i - 1][j];
- else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
-
- }
- }
5、举例推导dp数组
最后我们可以在纸上验证下结果是否与打印结果一致,若不一致,则仔细研究每一步的问题所在
最后附上代码供参考:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int SearchMv(vector<int>weight, vector<int>value, int square) {
//return 1;
/*vector<vector<int>>dp(weight.size(), vector<int>(square + 1, 0));
for (int i = weight[0]; i <= square; i++) {
dp[0][i] = value[0];
}
for (int i = 1; i < weight.size(); i++) {
for (int j = 1; j <= square; j++) {
if (weight[i] > j) {
dp[i][j] = dp[i - 1][j];
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
return dp[weight.size()-1][square];*/
vector<int>dp(square + 1, 0);
for (int i = 0; i < weight.size(); i++) {
for (int j = square; j >= 1; j--) {
if (j >= weight[i]) {
dp[j] = max(dp[j], (dp[j - weight[i]] + value[i]));
}
}
}
return dp[square];
}
int main() {
int m, n;
cin >> m;
cin >> n;
vector<int>weight(m, 0);
for (int i = 0; i < m; i++) {
cin >> weight[i];
}
vector<int>values(m, 0);
for (int i = 0; i < m; i++) {
cin >> values[i];
}
int maxValue = SearchMv(weight, values, n);
cout << maxValue << endl;
system("pause");
return 0;
}
这是母题,后面其衍生的问题我也会写出博客记录,希望可以对读者有一定的启发
相关问题:
1049. 最后一块石头的重量 II - 力扣(LeetCode)
这些问题我都会在后面写出心得体会
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。