你是一个货车司机CPU车斗容量有限背包容量。货场里有一堆货物物品每个货物有重量和价值。你的目标是在不超重的前提下装下价值最高的货物组合。模块一0-1 背包标准二维版1. 思路讲解定义dp[i][w]考虑前i件物品背包容量为w时能装的最大价值。对于第i件物品面临两个选择不装dp[i][w] dp[i-1][w]价值继承上一轮。装dp[i][w] dp[i-1][w-weight[i]] value[i]腾出空间加上价值。取两者最大值。2. 代码详解cppcpp#include vector #include algorithm using namespace std; class Solution { public: int knapsack(int N, int W, vectorint wt, vectorint val) { // dp[i][w]: 前i个物品容量w下的最大价值 vectorvectorint dp(N 1, vectorint(W 1, 0)); for (int i 1; i N; i) { // 遍历物品 for (int w 1; w W; w) { // 遍历容量 // 如果当前物品重量超过当前背包容量没法装 if (wt[i - 1] w) { dp[i][w] dp[i - 1][w]; } else { // 核心装 vs 不装 dp[i][w] max( dp[i - 1][w], // 不装 dp[i - 1][w - wt[i - 1]] val[i - 1] // 装 ); } } } return dp[N][W]; } };C 细节wt[i-1]是因为数组下标从 0 开始而 DP 下标从 1 开始为了省去初始化第 0 行的麻烦。模块二0-1 背包一维优化版 - 滚动数组1. 思路讲解观察二维 DP 表发现dp[i][...]只依赖于dp[i-1][...]。我们可以将二维压缩为一维dp[w]。关键难点为什么容量w必须倒序遍历如果正序遍历dp[w-weight[i]]可能已经被本轮第 i 个物品更新过了这就变成了“完全背包”物品可重复选取。倒序遍历能保证dp[w-weight[i]]一定是上一轮i-1的数据。2. 代码详解cppcppclass Solution { public: int knapsack(int N, int W, vectorint wt, vectorint val) { vectorint dp(W 1, 0); // 一维数组 for (int i 0; i N; i) { // 遍历物品 // 关键倒序遍历容量防止数据污染 for (int w W; w wt[i]; w--) { // dp[w] 相当于二维的 dp[i-1][w] // dp[w-wt[i]] 相当于二维的 dp[i-1][w-wt[i]] dp[w] max(dp[w], dp[w - wt[i]] val[i]); } } return dp[W]; } };口诀“0-1 背包倒着走完全背包顺着走”。模块三分割等和子集背包思想的应用1. 思路讲解能不能将一个数组分成两个和相等的子数组转化为能不能从数组中挑选一些数使得它们的和恰好等于sum/2。这是一个“背包容量为 sum/2物品重量为 nums[i]价值也为 nums[i]”​ 的 0-1 背包问题。2. 代码详解cppcppclass Solution { public: bool canPartition(vectorint nums) { int sum 0; for (int num : nums) sum num; if (sum % 2 ! 0) return false; // 奇数不可能平分 int target sum / 2; vectorbool dp(target 1, false); dp[0] true; // 什么都不选和为0永远成立 for (int num : nums) { // 遍历物品 // 遍历容量倒序0-1背包特性 for (int j target; j num; j--) { // 如果减去当前num剩下的重量能被凑出来那当前重量也能被凑出来 dp[j] dp[j] || dp[j - num]; } } return dp[target]; } };思路dp[j]是布尔类型表示能否凑出和为j。这里使用了逻辑或||。谢谢