目录
题目链接：01背包问题 二维
思路
①dp数组，物品从下标0到i的物品中任取，然后放进容量为j的背包里，此时最大的价值
②递推公式，到第i个物品时有两个选择，放或者不放。如果不放，最大价值就是dp[i-1][j]，说明第i个物品太大了放不下，价值还是和i-1的状态一样；如果放，最大价值就是i-1时的价值加上value[i]，即dp[i-1][j-wight[i]]+value[i]。也就是说当前dp[i][j]可以由这两个状态推导而来，因为要取最大价值，所以取这两个值中的最大值
③dp数组初始化，由递推公式可知，dp数组当前值可由左上角和正上方两个方向推导而来， 所以只需要初始化第一列和第一行即可由递推公式得到整个二维dp数组。当背包容量为0时，放不了东西，所以这一列初始化为0；下标为物品0时，如果背包容量足够就将其初始化为物品0的价值，如果放不下就初始化为0
④遍历顺序，由递推公式可知，只要有左上角和上方的值即可推导当前值，所以先遍历行或者列，或者说先遍历物品或者背包都可以
⑤推导dp数组
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int m,n;//m为物品个数，n为背包空间
void solve(){
vector<int> weight(m,0);//物品重量
vector<int> value(m,0);//物品价值
vector<vector<int>> dp(m,vector<int>(n+1,0));//dp数组
//输入重量和价值
for(int i = 0; i < m; i++){
cin>>weight[i];
}
for(int i = 0; i < m; i++){
cin>>value[i];
}
//当第一个物品的重量小于背包空间时
//此时dp赋值为该物品的value
for(int j = weight[0]; j <= n; j++){
dp[0][j] = value[0];
}
//遍历背包
for(int j = 0; j <= n; j++){
//遍历物品，物品从1到i
for(int i = 1; i < m; i++){
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]);
}
}
cout<<dp[m-1][n]<<endl;
}
int main(){
while(cin>>m>>n){
solve();
}
return 0;
}题目链接：01背包问题 一维
思路
①dp数组，容量为j的背包，能装的物品价值最大为dp[j]
②递推公式，与二维类似，只不过用了一维的滚动数组。此时背包空间为j，有两个选择：装不下当前物品，则此时背包的价值与遍历上一个物品时一样，也就是dp[j] = dp[j-weight[i]]；能装下时，有两种情况，装完后价值比之前大，装完后价值比之前小，肯定是二者选最大。装之前，dp[j] = dp[j-weight[i]]，装之后，dp[j] = dp[j-weight[i]] + value[i]。
③dp数组初始化，根据递推公式可知背包空间为0时装不了物品，所以价值为0即dp[0] = 0，往后遍历时会进行更新，所以其他位置先初始化为0即可。
④遍历顺序，先物品，后背包，且背包倒序遍历，从空间最大往前遍历。因为是先遍历物品，如果背包正序遍历，则物品i可能会被重复放入。
⑤推导dp数组
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//一维dp数组
int m,n;//m为物品种类，n为背包容量
void solve(){
vector<int> weight(m,0);
vector<int> value(m,0);
//dp[n]的意义是背包容量为n的时候，所装物品的最大价值为dp[n]
//因为dp数组从0开始，所以dp数组的大小为n+1
vector<int> dp(n+1,0);
//输入物品信息，重量和价值
for(int i = 0; i < m; i++){
cin>>weight[i];
}
for(int i = 0; i < m; i++){
cin>>value[i];
}
//遍历顺序，先物品，后背包，其背包倒序遍历
//由于dp数组大小有限，并不会保存上一层的信息
//所以要先遍历物品，把当前物品处理完再进行下一层
//背包倒序遍历是防止同一物品被多次装入背包
for(int i = 0; i < m; i++){
//如果能装下才对dp数组当前位置进行更新
for(int j = n; j >=weight[i]; j--){
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
cout<<dp[n]<<endl;
}
int main(){
while(cin>>m>>n){
solve();
}
return 0;
}题目链接：416. 分割等和子集
思路
将该题归类为01背包问题
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
①dp数组，容量为j的背包所装物品的最大价值为dp[j]，本题所给的数组既是重量也是价值
②递推公式，dp[j] = max[dp[j], dp[j-nums[i]]+nums[i]]
③dp数组初始化，本题所给数组中的数都是正整数，所以初始化为0即可
④遍历顺序，滚动数组，先物品后背包，背包倒序
⑤推导dp数组
代码
class Solution {
public:
bool canPartition(vector<int>& nums) {
// 计算数组中所有元素之和
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 如果和为奇数，则不可能分隔，因为都是数组中都为正整数
if (sum % 2 == 1)
return false;
// target为背包的容量
int target = sum / 2;
vector<int> dp(target + 1, 0); // 定义dp数组
// 01背包，先物品，后背包，背包倒序遍历
for (int i = 0; i < nums.size(); i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if (dp[target] == target)
return true;
return false;
}
};总结
①01背包问题，m个物品，有各自的重量和价值，背包容量为n，将物品装入到背包里，使得背包中物品的价值总和最大
②选择背包大小为dp数组，dp[j]的含义是背包容量为j时装入物品的最大价值
③再遍历dp数组时，每次都有两个选择，装与不装。当容量不足时就不装，价值与上一状态一样；当容量足够时，装入当前物品有一个价值，上一状态也有一个价值，取最大值
④416.分割等和子集竟然能用01背包解决，属实是意想不到
⑤刚开始接触背包问题，很多细节没有掌握，需要复习