背包问题详解：从入门到精通
目录
简介
背包问题：简单来说就是给一堆自带属性物品和自带属性的背包
挑选一些物品放到背包里面，让价值最大
物品分为：能选一个还是无穷个
背包分为：必须装满还是不必装满
由此衍生出来的问题就多达4种
实际中个数还有其他分类，所以背包问题实际可以分为很多类，这里只讲这四类，并且所有的背包问题都应该以01背包为基础，所有变种均源自01背包
背包问题是动态规划中最经典的分支之一，核心是「在有限容量下，选择物品组合以最大化 / 最小化目标值」，所有背包问题都遵循「状态定义→转移逻辑→初始化」的统一框架，差异仅在「物品能否重复选」「背包是否分维度」「目标是最值 / 可行性 / 方案数」。
题型 核心特征 典型场景 01 背包 每件物品只能选 0 次或 1 次 选物品装背包，每件仅一个 完全背包 每件物品可以选无限次 凑零钱，硬币无限供应 多重背包 每件物品有固定数量限制 选物品装背包，每件有 n 个 多维背包 背包有多个容量维度（如重量 + 体积） 选物品需同时满足重量和体积
01背包
线性dp问题
状态表示：如果以某个位置为结尾，这时候是推不出来状态转移方程的，因为你不知道剩余的体积是多少，你填写i位置的时候，不知道前面用了多少体积
很明显需要两个状态
dp[i][j]：表示从前i个物品当中选，总体积不超过j的所有选法中，价值最大的
注意j-v[i]可能不存在，因为当你i位置的体积过大的时候，往前面找就没有剩余空间
初始化这里由于我们一开始的物品下标从1开始，天然就多加了一行多加了一列
填表顺序看当前位置依赖哪个位置的填写
由此，第二问是背包刚好被装满，对应01背包正好装满
那状态表示也很容易
dp[i][j]：表示从前i个物品当中选，总体积恰好等于j的所有选法中，价值最大的
注意：我们这里采用dp[i][j]==-1表示这种情况凑不出来j体积
对于不选i物品，我们可以不用判断，前面凑不出来直接继承即可
但是对于第二种情况，如果前面凑不出来，那dp[i][j]=-1
dp[i][j]的取值含义必须和「问题目标」强绑定，0 有明确的业务意义（比如 “价值为 0”“方案数为 0”），无法表示 “凑不出”，而 - 1（或无穷大）是专门的 “不可行标记”。否则你在填写某个位置的时候，怎么判断前面能不能装满呢？假设你当前所剩体积为5，你要想前查找，那dp[i-1][5]，那这个dp[i-1][5]=0的话，这个0是表示装满5体积之后的最大价值为0呢还是凑不出来呢？有歧义，你的状态表示就无法更新，如果你硬要用就会导致dp[i][j]的状态被更新，实际凑不出来，但是你更新完dp[i][j]之后能凑出来，那你所有的状态都错了
初始化：
空间优化
当我们发现当前状态仅仅依赖有限的行数的时候，可以采用固定的行数数组来优化，因为这里我们仅仅用到i-1行，所以仅仅需要两行数组就可以更新完毕
更绝的优化就是用一行，仅仅需要填写当前位置的时候覆盖即可
主要要从右往左填写，不能左往右，因为左往右当右边用到左边的时候会形成覆盖，应该从右往左，这样右边用到的值才是有效的
分隔等和子集
本题最重要的就是转换问题，把问题转换成01背包，也就是sum/2是背包容量
class Solution { public: bool canPartition(vector<int>& nums) { // 转换为01背包必须装满问题，容量为sum/2 int m = nums.size(); int sum = 0; for (int i = 0; i < m; i++) { sum += nums[i]; } if (sum % 2 != 0) return false; int v = sum / 2; vector<vector<int>> dp(m + 1, vector<int>(v + 1)); for (int j = 1; j < v + 1; j++) { dp[0][j] = -1; } for (int i = 1; i < m + 1; i++) { for (int j = 1; j < v + 1; j++) { dp[i][j] = dp[i - 1][j]; if (j - nums[i - 1] >= 0 && dp[i - 1][j - nums[i - 1]] != -1) dp[i][j] =max(dp[i][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]); } } return dp[m][v] == -1 ? false : true; } }; class Solution { public: bool canPartition(vector<int>& nums) { // 转换为01背包必须装满问题，容量为sum/2 int m = nums.size(); int sum = 0; for (int i = 0; i < m; i++) { sum += nums[i]; } if (sum % 2 != 0) return false; int v = sum / 2; vector<vector<bool>> dp(m + 1, vector<bool>(v + 1)); for (int i = 0; i < m + 1; i++) { dp[i][0] = true; } for (int i = 1; i < m + 1; i++) { for (int j = 1; j < v + 1; j++) { dp[i][j] = dp[i - 1][j]; if (j - nums[i - 1] >= 0 && dp[i - 1][j - nums[i - 1]] != false) dp[i][j] = true; } } return dp[m][v]; } };
优化版本
class Solution { public: bool canPartition(vector<int>& nums) { // 转换为01背包必须装满问题，容量为sum/2 int m = nums.size(); int sum = 0; for (int i = 0; i < m; i++) { sum += nums[i]; } if (sum % 2 != 0) return false; int v = sum / 2; vector<bool> dp(v + 1); dp[0] = true; for (int i = 1; i < m; i++) { for (int j = v; j >= nums[i - 1]; j--) { if (dp[j - nums[i - 1]] != false) dp[j] = true; } } return dp[v]; } };
目标和
也是需要转换，a-b=target，a+b=sum
所以a=（target+sum）/2
也就是01背包问题，刚好装满(target+sum)/2的体积
这里不用初始化的原因是，这一行填写的时候压根不会越界，因为j>=nums[i]已经限制住了，此时j==0，nums[i]只有=0才会进入选i那个分支，然后沿用上面的1
class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int m = nums.size(); int sum = 0; for (int i = 0; i < m; i++) { sum += nums[i]; } if ((target + sum) % 2 != 0 || target + sum < 0) { return 0; } int aim = (target + sum) / 2; vector<vector<int>> dp(m + 1, vector<int>(aim + 1)); dp[0][0] = 1; for (int i = 1; i < m + 1; i++) { for (int j = 0; j < aim + 1; j++) { dp[i][j] += dp[i - 1][j]; if (j >= nums[i - 1]) { dp[i][j] += dp[i - 1][j - nums[i - 1]]; } } } return dp[m][aim]; } };
这里j==0的话就是因为刚刚没有初始化第一列
最后一块石头的重量Ⅱ
1049. 最后一块石头的重量 II - 力扣（LeetCode）
读题的时候根据示例就有点发现，选一堆数，在选一堆数，使得这两堆数碰撞即a-b的差值最小
本题类似分隔子集，也就是给你一堆数，能均分成两堆就均分成两堆，不能的话尽量使得他们的差值缩小
这样我们可以转换成01背包问题中，背包容量为sum/2，但是可以不必装满，因为不一定均分
然后用sum-2*dp[m][v]即可，因为其中两堆互相抵消，sum减掉就是剩下的石头了
容量为sum/2即可，因为你如果是判断奇数偶数都一样的，我们只要尽可能的让它接近sum/2，因为最后的石头重量是拿大的那一堆减小的那一堆，我们只要寻找小的那一堆，最接近均分值即可（对应小的那一堆尽量靠近sum/2）
这些题的本质就是如何转换成背包问题，然后采用背包的思想，背包问题的代码不是直接抄，而是采取思想，选这个物品还是不选，选就要往前找j-nums[i]的最大重量
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int m = stones.size();
int sum = 0;
for (int i = 0; i < m; i++) {
sum += stones[i];
}
int v = sum / 2;
vector<vector<int>> dp(m + 1, vector<int>(v + 1));
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < v + 1; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= stones[i - 1]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
}
}
}
return sum - 2 * dp[m][v];
}
};完全背包
完全背包就是物品可以选无穷个，体积分两种：必须装满和不必装满
很明显你采用之前的状态表示去推导状态转移方程
肯定出现j-nums[i]，j-2*nums[i]，j-3*nums[i]……往前寻找这些的最值
这就有点像子数组和子序列，子序列需要往前寻找最优解
无非就是三层for循环，O(n^3)
这有点像我们之前的通配符匹配问题
在那里我们说过如果一个状态由其他很多状态组成，可以采用数学的思想
那这里照样可以优化
数学方式：
dp[i][j]=max(dp[i-1][j]，dp[i-1][j-v[i]]+w[i]，dp[i-1][j-2v[i]]+2w[i]，dp[i-1][j-3v[i]]+3w[i]……)
dp[i][j-v[i]]+w[i]=max(dp[i-1][j-v[i]]+w[i]，dp[i-1][j-2v[i]]+2w[i]，dp[i-1][j-3v[i]]+3w[i]……)
dp[i][j]=max(dp[i-1][j]，dp[i][j-v[i]]+w[i])
这就有点像高中的裂项相消一样，找规律怎么裂，怎么消
初始化中第一列除了dp[0][0]都可以不用初始化，因为我们在填表的时候会判断j-v[i]是否大于0，所以不会越界
然后看依赖关系去决定填表顺序
第二问：必须装满
dp[i][j]：表示从前i个物品当中选，体积刚好等于j的所有选法当中，价值最大的
很明显和01背包一样，如果凑不齐我们需要把dp[i][j]==-1
使用前我们需要判断是否=-1，不是才可以用
如果你不是使用-1去区别，不加判断，可能会导致dp[i][j-v[i]]+w[i]在去max后被dp[i][j]使用，但是你前面都凑不齐你还使用，会导致后面所有的状态出错
初始化：
优化：采用滚动数组
这里和01背包不同的是从左往右遍历，因为填写dp[i][j]的时候是需要别的已经更新了
你想用之前的状态就是从右往左遍历
想用更新之后的状态就左往右遍历
零钱兑换
初始化这里两个方法：
1：初始化为-1，每次判断一下能不能凑成
2：由于是求min，所以我们初始化成一个非常大的数，导致这个不能凑成的方案不会被选中
如果采用第二种方法，返回值的时候需要判断一下
class Solution { public: int coinChange(vector<int>& coins, int amount) { int m = coins.size(); if (amount == 0) { return 0; } vector<vector<int>> dp(m + 1, vector<int>(amount + 1)); for (int j = 1; j < amount + 1; j++) { dp[0][j] = -1; } for (int i = 1; i < m + 1; i++) { for (int j = 0; j < amount + 1; j++) { dp[i][j] = dp[i - 1][j]; if (j >= coins[i - 1] && dp[i][j - coins[i - 1]] != -1) { int candidate = dp[i][j - coins[i - 1]] + 1; // 选当前硬币，数量+1 // 如果上一行不可行，直接赋值；否则取最小值 if (dp[i][j] == -1) { dp[i][j] = candidate; } else { dp[i][j] = min(dp[i][j], candidate); } } } } return dp[m][amount]; } };如果你用-1表示，那不选的时候直接继承即可，但是选1个2个3个的时候先判断，如果前面能凑成，我们需要判断如果不选的时候直接继承是-1，我们需要覆盖，否则取min
不然取min的时候会选到-1
优化版本
class Solution { public: int coinChange(vector<int>& coins, int amount) { int m = coins.size(); if (amount == 0) { return 0; } vector<int> dp(amount + 1); for (int j = 1; j < amount + 1; j++) { dp[j] = -1; } for (int i = 1; i < m + 1; i++) { for (int j = 0; j < amount + 1; j++) { if (j >= coins[i - 1] && dp[j - coins[i - 1]] != -1) { int candidate = dp[j - coins[i - 1]] + 1; // 选当前硬币，数量+1 // 如果上一行不可行，直接赋值；否则取最小值 if (dp[j] == -1) { dp[j] = candidate; } else { dp[j] = min(dp[j], candidate); } } } } return dp[amount]; } };记得从左往右填表
以下是采用0x3f3f3f3f的写法
零钱兑换Ⅱ
分析思路是一样的，注意数学变换一下即可
然后dp[0][0]=1
因为0种物品凑成0就是1种选法了
由于题目说可能+之间会超过最大INT，所以我们初始化时需要初始化成double
class Solution { public: int change(int amount, vector<int>& coins) { int m = coins.size(); vector<vector<double>> dp(m + 1, vector<double>(amount + 1)); dp[0][0] = 1; for (int i = 1; i < m + 1; i++) { for (int j = 0; j < amount + 1; j++) { dp[i][j] = dp[i - 1][j]; if (j >= coins[i - 1]) { dp[i][j] += dp[i][j - coins[i - 1]]; } } } return dp[m][amount]; } };
完全平方数
这道题分析完之后，就是从1，4，9，16……等平方数中挑选一些数，使其刚好等于n
那这不就是完全背包问题
由于你选的平方数肯定是小于n的，比如13，你选的最大的肯定是比根号13小的
那这样你只需要开根号13+1的大小即可
一和零
这就是背包问题，背包问题就是给一堆物品，在背包的限制下，挑选出满足条件，比如最大价值等
二维费用的背包问题的核心就是「背包有两个维度的限制条件」（比如 “重量 + 体积”“重量 + 价值”“数量 + 时间” 等），所有物品的选择都必须同时满足这两个限制，最终求最大化 / 最小化目标值（如最大价值）。
所以这道题的本质就是二维的01背包问题
很明显一个限制条件是j，那是不是在来一个限制就是k
所以是dp[i][j][k]
那很明显，这是三维dp问题，肯定是三层for循环
初始化的时候也仅仅需要考虑i=0的时候即可，因为j=0和k=0的时候通过j>=a&&k>=b特判过
class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { int len = strs.size(); vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1))); for (int i = 1; i < len + 1; i++) { int a = 0, b = 0; for (auto ch : strs[i - 1]) { if (ch == '0') a++; else b++; } for (int j = 0; j < m + 1; j++) { for (int k = 0; k < n + 1; k++) { dp[i][j][k] = dp[i - 1][j][k]; if (j >= a && k >= b) { dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1); } } } } return dp[len][m][n]; } };优化版本：滚动数组
注意这里是从大到小遍历，因为当前状态依赖的状态会用到旧值
class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { int len = strs.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 1; i < len + 1; i++) { int a = 0, b = 0; for (auto ch : strs[i - 1]) { if (ch == '0') a++; else b++; } for (int j = m; j >= 0; j--) { for (int k = n; k >= 0; k--) { dp[j][k] = dp[j][k]; if (j >= a && k >= b) { dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1); } } } } return dp[m][n]; } };
盈利计划
本题也是一个二维的01背包问题
就是在profit中挑选一些数，使得这些数的总和超过minprofit，并且group的总和不超过n
最重要的是思考这个k-p[i]能否小于0，是可以的，比如k-p[i]<0时，则k<p[i]，说明当前的利润足够大，但是我们的数组的下标又没有<0的情况，所以要特判，
当k<p[i]时，要去找dp[i-1][j-g[i]][0]：意思是前i-1个数挑选，总人数不超过j-g[i]，总利润至少为0，一共有多少种选法，加上i位置的人数和利润肯定符合
这也是这道题的难点，就是至少
初始化这里的意思是，当前任务为0，总人数不超过j，总利润为0，那就是什么都不做，那就是空集，那就是初始化为1
class Solution { public: int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) { const int MOD = 1e9 + 7; int len = g.size(); vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(m + 1))); for (int j = 0; j < n + 1; j++) dp[0][j][0] = 1; for (int i = 1; i <= len; i++) { for (int j = 0; j <= n; j++) { for (int k = 0; k <= m; k++) { dp[i][j][k] = dp[i - 1][j][k]; if (j >= g[i - 1]) dp[i][j][k] +=dp[i - 1][j - g[i - 1]][max(0, k - p[i - 1])]; dp[i][j][k] %= MOD; } } } return dp[len][n][m]; } };优化版本
注意遍历顺序，01背包是从大到小
似包非包问题：组合总和
本题读完之后，是高中的排列问题，而不是组合问题，排列讲究顺序，所以本题是排列问题
但是背包问题是用来解决组合问题的，组合就是从一堆数当中挑不讲究顺序的
一开始学习dp的时候就说过，dp无非就是递推版本，记忆化搜索是递归版本，两个都大量的剪枝所以时间复杂度才低
所以当发现重复子问题的时候需要抽象出来
class Solution { public: int combinationSum4(vector<int>& nums, int target){ vector<double>dp(target+1); dp[0]=1; for(int i=1;i<target+1;i++) { for(auto x:nums) { if(i>=x) { dp[i]+=dp[i-x]; } } } return dp[target]; } };
不同的二叉搜索树：卡特兰数的应用
当以j为根节点的时候，左边有j-1个，右边有i-j个，主要要相乘
递推公式就是卡特兰数的递推公式
class Solution { public: int numTrees(int n) { vector<int> dp(n + 1); dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[i - j] * dp[j - 1]; } } return dp[n]; } };
总结
至此，背包问题基本研究完毕
无非就是背包的限制条件和选的数有啥特点
背包问题解决的是组合问题
01背包
完全背包
优化点：数学优化、滚动数组（注意遍历顺序，01背包从右往左，完全从左往右，本质是看当前填写的状态是个什么依赖条件）
背包问题是动态规划的经典分支，核心是在有限约束下选择物品组合，最大化 / 最小化目标值，所有题型都遵循「状态定义→转移逻辑→初始化」的统一框架，差异仅在于「物品选择规则」和「约束维度」。
核心分类（按物品选择规则）
表格
背包类型 核心特征 关键遍历顺序（一维版） 典型场景 01 背包 每件物品选 0/1 次 逆序遍历容量 分割等和子集、最后一块石头重量 II 完全背包 每件物品可无限选 正序遍历容量 零钱兑换、组合总和 IV 多重背包 每件物品有固定数量限制 拆分为 01 背包（逆序） 有限数量物品装背包 二维费用背包 背包有 2 个约束（如重量 + 体积） 双维度逆序 / 正序遍历 同时限制重量和体积的选品 核心记忆点
- 核心逻辑：背包问题的本质是「选 / 不选」的状态转移，遍历顺序决定物品是否可重复选；
- 初始化：0 是 “合法空状态”，-1/INT_MAX 是 “不可行标记”，不可混用；
- 优化方向：一维数组是最优写法，二维费用仅多一层循环，规则不变；
- 题型识别：看到 “选物品、有限约束、最值 / 方案数”，优先往背包模型转化。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
10
0- 0
已为社区贡献1条内容
所有评论(0)