01背包问题（二维动态规划法）的时间复杂度与空间复杂度

摘要本文分析01背包问题的二维动态规划解法。定义物品数量为N、背包容量为W状态dp[i][j]表示前i件物品在容量j下的最大价值。通过双重循环填充(N1)×(W1)表格每格O(1)计算得到时间复杂度O(N×W)存储完整二维数组空间复杂度同为O(N×W)。代码示例采用Java实现。文末补充一维滚动数组优化可将空间降至O(W)但时间复杂度不变。本文重点阐明复杂度指标与符号含义帮助读者清晰理解二维DP的性能瓶颈。ps图片来源网络侵删目录一、先给结论开门见山二、问题定义与符号说明三、二维DP解法详解1. 状态定义2. 状态转移方程3. 边界条件四、时间复杂度分析核心五、空间复杂度分析核心六、二维DP完整代码示例Java七、关于一维空间优化的补充仅为提及总结一、先给结论开门见山对于01背包问题使用二维动态规划DP求解时时间复杂度为O(N × W)空间复杂度为O(N × W)其中N代表物品的总个数W代表背包的最大容量即最大承重/体积。这两个符号将贯穿全文。二、问题定义与符号说明给定N件物品编号从 1 到N。第i件物品的重量为weight[i]价值为value[i]。现有背包的最大承重为W。每件物品只能选择放入1或放弃0求解在不超过背包承重的前提下背包内物品的最大总价值是多少。符号约定N物品的数量W背包的容量限制最大承重weight[i]第i件物品的重量value[i]第i件物品的价值三、二维DP解法详解1. 状态定义我们定义一个二维数组dp[i][j]其含义为只考虑前i件物品即第 1 到第i件在背包当前承重上限为j的情况下能够获得的最大总价值。其中i的取值范围是[0, N]j的取值范围是[0, W]。2. 状态转移方程面对第i件物品重量weight[i]价值value[i]我们只有两种选择不选第i件物品那么当前最大价值就等于前i-1件物品在容量j下的最大价值即dp[i-1][j]。选第i件物品前提是当前容量j必须 ≥weight[i]此时背包剩余容量变为j - weight[i]价值为前i-1件物品在该剩余容量下的最大价值加上当前物品价值即dp[i-1][j - weight[i]] value[i]。综合两者取最大值转移方程为当 j weight[i] 时 dp[i][j] dp[i-1][j] 当 j ≥ weight[i] 时 dp[i][j] max( dp[i-1][j], dp[i-1][j - weight[i]] value[i] )3. 边界条件当i 0时没有物品任何容量下的价值都是 0dp[0][j] 0当j 0时背包容量为0任何物品都放不下价值也是 0dp[i][0] 0四、时间复杂度分析核心我们采用双层嵌套循环来填充这个(N1) × (W1)的二维表格外层循环遍历每一件物品i从 1 到N共循环N次。内层循环遍历背包容量的每一个刻度j从 0 到W共循环W 1次复杂度量级记作W次。在循环体的内部无论是判断语句if (j weight[i])还是求最大值的操作max()都只涉及基本的比较和整数加法这些操作均属于常数时间即O(1)。因此程序运行所需的总基本操作次数为总次数 N × W × O(1)忽略常数项后得出时间复杂度为T(N, W) O(N × W)特别注意这是一个伪多项式时间复杂度。因为W在计算机中是以二进制长度存储的数值其数值大小是指数级的。但在算法竞赛和常规面试中我们默认将N和W看作输入规模并以此作为复杂度衡量标准。五、空间复杂度分析核心二维DP解法需要维护一个完整的二维数组dp[N1][W1]。该数组总共包含(N 1) × (W 1)个元素。在大多数编程语言如 C、Java、Python中每个元素存储一个整型数值通常占 4 或 8 个字节。为了衡量数量级我们忽略常数系数和低阶项得到数组占用的总空间为总空间 (N1) × (W1) ≈ N × W因此空间复杂度为S(N, W) O(N × W)当N 1000W 1000时数组大小约为 100 万个单位内存尚可接受但当N 10^4W 10^4时数组将膨胀到 1 亿个单位内存占用将变得非常可观约 400 MB 以上这也是二维DP的主要瓶颈所在。六、二维DP完整代码示例Javapublic class Knapsack2D { public static int knapsack2D(int N, int W, int[] weight, int[] value) { // 初始化二维DP表默认值为0 int[][] dp new int[N 1][W 1]; // 遍历每一件物品 for (int i 1; i N; i) { for (int j 0; j W; j) { // 1. 默认不选第i件物品 dp[i][j] dp[i - 1][j]; // 2. 如果容量足够尝试选第i件物品取最大值 if (j weight[i]) { dp[i][j] Math.max(dp[i][j], dp[i - 1][j - weight[i]] value[i]); } } } // 返回前N件物品、容量W下的最大价值 return dp[N][W]; } public static void main(String[] args) { int N 4, W 8; // 下标从1开始占位0 int[] weight {0, 2, 3, 4, 5}; int[] value {0, 3, 4, 5, 6}; System.out.println(最大价值为 knapsack2D(N, W, weight, value)); } }七、关于一维空间优化的补充仅为提及由于dp[i][j]的状态转移只依赖于上一行dp[i-1][...]的数据因此我们可以将二维数组压缩为一维数组滚动数组将空间复杂度优化为 O(W)。但必须注意压缩为一维后内层循环j必须采用逆序从W递减到weight[i]遍历以防止同一件物品被重复累加。尽管如此时间复杂度的量级并不会改变依然为O(N × W)。总结实现方式时间复杂度空间复杂度核心依赖二维DPO(N × W)O(N × W)完整的二维状态表一维DP优化O(N × W)O(W)逆序滚动数组再次强调本文重点讨论的二维DP其时间复杂度O(N × W)由双重循环决定空间复杂度O(N × W)由二维数组大小决定。其中N是物品个数W是背包容量重量限制。希望这次严格按照符号规范的讲解能帮您彻底理清这两个指标如有疑问欢迎留言讨论。