背包DP：从入门到精通的动态规划指南

背包DP的基本概念背包动态规划Knapsack DP是一类经典的优化问题通常描述为给定一组物品每个物品有重量和价值在不超过背包承重限制的前提下选择物品使得总价值最大。背包问题分为多种类型如0-1背包、完全背包、多重背包等。0-1背包问题0-1背包是最基础的背包问题每个物品只能选择一次选或不选。其状态转移方程为 [ dp[i][j] \max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) ] 其中( dp[i][j] ) 表示前 ( i ) 个物品在背包容量为 ( j ) 时的最大价值( w[i] ) 和 ( v[i] ) 分别为第 ( i ) 个物品的重量和价值。实现代码int knapsack_01(vectorint weights, vectorint values, int capacity) { int n weights.size(); vectorvectorint dp(n 1, vectorint(capacity 1, 0)); for (int i 1; i n; i) { for (int j 0; j capacity; j) { if (j weights[i-1]) { dp[i][j] max(dp[i-1][j], dp[i-1][j-weights[i-1]] values[i-1]); } else { dp[i][j] dp[i-1][j]; } } } return dp[n][capacity]; }空间优化由于状态转移只依赖前一行可以将二维数组优化为一维数组int knapsack_01_optimized(vectorint weights, vectorint values, int capacity) { vectorint dp(capacity 1, 0); for (int i 0; i weights.size(); i) { for (int j capacity; j weights[i]; --j) { dp[j] max(dp[j], dp[j - weights[i]] values[i]); } } return dp[capacity]; }完全背包问题完全背包允许每个物品选择多次。状态转移方程为 [ dp[i][j] \max(dp[i-1][j], dp[i][j-w[i]] v[i]) ] 注意与0-1背包的区别完全背包的状态转移是从同一行更新。实现代码int knapsack_unbounded(vectorint weights, vectorint values, int capacity) { vectorint dp(capacity 1, 0); for (int i 0; i weights.size(); i) { for (int j weights[i]; j capacity; j) { dp[j] max(dp[j], dp[j - weights[i]] values[i]); } } return dp[capacity]; }多重背包问题多重背包限制每个物品最多选择 ( k[i] ) 次。可以通过二进制拆分或单调队列优化实现。二进制拆分实现将每个物品拆分为多个“虚拟物品”转化为0-1背包问题int knapsack_bounded(vectorint weights, vectorint values, vectorint counts, int capacity) { vectorint dp(capacity 1, 0); for (int i 0; i weights.size(); i) { int k 1; while (k counts[i]) { int w k * weights[i]; int v k * values[i]; for (int j capacity; j w; --j) { dp[j] max(dp[j], dp[j - w] v); } counts[i] - k; k * 2; } if (counts[i] 0) { int w counts[i] * weights[i]; int v counts[i] * values[i]; for (int j capacity; j w; --j) { dp[j] max(dp[j], dp[j - w] v); } } } return dp[capacity]; }背包问题的变种恰好装满背包初始化时 ( dp[0] 0 )其余为 ( -\infty )确保只有恰好装满的状态才有效。方案计数修改状态转移方程累加方案数而非取最大值 [ dp[j] dp[j - w[i]] ]多维费用背包增加状态维度例如限制体积和重量 [ dp[i][j][k] \max(dp[i-1][j][k], dp[i-1][j-v1[i]][k-v2[i]] w[i]) ]常见例题分析分割等和子集LeetCode 416问题转化为0-1背包判断是否能选出部分元素和为总和的一半bool canPartition(vectorint nums) { int sum accumulate(nums.begin(), nums.end(), 0); if (sum % 2 ! 0) return false; int target sum / 2; vectorbool dp(target 1, false); dp[0] true; for (int num : nums) { for (int j target; j num; --j) { dp[j] dp[j] || dp[j - num]; } } return dp[target]; }零钱兑换LeetCode 322完全背包问题求最小硬币数int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, amount 1); dp[0] 0; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] min(dp[j], dp[j - coin] 1); } } return dp[amount] amount ? -1 : dp[amount]; }背包DP的优化技巧滚动数组通过交替使用两行数组减少空间复杂度。单调队列优化适用于多重背包将时间复杂度从 ( O(N \cdot V \cdot K) ) 降为 ( O(N \cdot V) )。常数优化在内层循环中提前终止或调整遍历顺序。常见错误与调试初始化错误未正确处理边界条件如容量为0时的初始化。遍历顺序错误0-1背包必须逆序遍历容量完全背包需正序遍历。状态转移混淆注意区分“选”与“不选”时的状态来源当前行或上一行。背包DP的扩展应用树形背包在树结构上进行DP通常结合后序遍历实现。分组背包每组物品只能选一个增加一维状态表示组别。依赖背包物品之间存在依赖关系需转化为树形结构处理。总结背包DP的核心在于状态定义和转移方程的设计。通过分析问题类型0-1、完全、多重和约束条件容量、费用维度选择合适的实现方式。优化空间复杂度和时间复杂度是提高效率的关键而变种问题则需要灵活调整状态转移逻辑。