如何将背包问题的时间复杂度从O(N*M)优化至O(N)？

空间复杂度优化：从O(2*M)降到O(M) #

你当前采用的两轮数组滚动优化已经是空间压缩的一步，但还能进一步简化为一维数组实现，核心是逆序遍历背包容量：

• 初始化长度为M+1的数组dp，其中dp[j]代表容量为j的背包能容纳的最大总重量（或最大总价值，依你的问题目标而定）。
• 遍历每个物品时，从j = M倒序遍历到j = weight[i]，更新规则为：
  • 若目标是最大总重量：dp[j] = max(dp[j], dp[j - weight[i]] + weight[i])
  • 若目标是最大总价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
• 逆序遍历的目的是确保每个物品只被计算一次，避免重复选取（符合01背包的约束）。这种方法把空间复杂度直接压缩到O(M)，时间复杂度仍保持O(M*N)，代码实现也更简洁。

时间复杂度的优化思路 #

01背包问题的通用时间复杂度下界是O(N*min(M, S))（S为所有物品的总重量），无法突破这个下界，但可以根据问题特性减少实际计算量：

• 当物品总重量S ≤ M时：将dp数组长度设为S+1而非M+1，此时时间复杂度变为O(N*S)，若S远小于M，能显著减少循环次数。
• 分组处理重复重量物品：如果存在大量重量相同的物品，可以将它们按价值排序后分组处理，减少遍历次数。
• 分支定界剪枝：如果需要快速找到最优解（而非遍历所有情况），分支定界法可以通过预估剩余物品的最大可能价值/重量，提前剪掉不可能得到更优解的分支，在平均情况下提升效率，但最坏时间复杂度仍为O(M*N)。

内容的提问来源于stack exchange，提问作者Jack Duan