当前位置：首页 > news >正文

代码随想录算法训练营第三十九天| 01背包问题二维、一维、416. 分割等和子集

news 2026/5/12 14:15:08

46. 携带研究材料（二维）

思路：dp[i][j] 中i，j分别表示表示物品和背包容量。dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。在放物品时，有以下情况：
不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值。
递归公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
在二维中遍历顺序正反都可以。

我的代码：

#include <bits/stdc++.h> using namespace std; int main() { int n,bagweight; cin>>n>>bagweight; vector<int> weight(n,0); vector<int> value(n,0); for(int i=0;i<n;i++) { cin>>weight[i]; } for(int i=0;i<n;i++) { cin>>value[i]; } vector<vector<int>> dp(n,vector<int>(bagweight+1,0)); for(int i=0;i<n;i++) { dp[i][0]=0; } for(int i=weight[0];i<=bagweight;i++) { dp[0][i]=value[0]; } for(int i=1;i<n;i++) { for(int j=1;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]); } } } cout<<dp[n-1][bagweight]<<endl; return 0; } #include <bits/stdc++.h> using namespace std;

46. 携带研究材料（一维）

思路：在二维的时候，我们可以发现：如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])；与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]。在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。一维中必须先遍历物品再遍历背包，并且要倒序遍历背包，这样才不会重复选择。

我的代码：

#include <bits/stdc++.h> using namespace std; int main() { int n,bagweight; cin>>n>>bagweight; vector<int> weight(n,0); vector<int> value(n,0); for(int i=0;i<n;i++) { cin>>weight[i]; } for(int i=0;i<n;i++) { cin>>value[i]; } vector<int> dp(bagweight+1,0); for(int i=0;i<n;++i) { for(int j=bagweight;j>=weight[i];j--) { dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); } } cout<<dp[bagweight]<<endl; return 0; }

416. 分割等和子集

思路：首先，本题要求集合里能否出现总和为 sum / 2 的子集。既有一个只能装重量为 sum / 2的背包，商品为数字，这些数字能不能把这个背包装满。一个数字只有一个维度，即重量等于价值。当数字可以装满承载重量为 sum / 2 的背包的背包时，这个背包的价值也是 sum / 2。那么这道题就是装满了载重量为 sum / 2 的背包，如果最大价值是 sum / 2，说明正好被商品装满了。因为商品是数字，重量和对应的价值是相同的。dp[j]的数值一定是小于等于j的。当 dp[target] == target 的时候，背包就装满了。

我的代码：

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; int target=sum/2; vector<int> dp(10001,0); 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; } };