动态规划中，为何完全背包用一维数组、0/1背包用二维数组？

嘿，这个问题问到了背包问题状态优化的核心本质！其实核心差异来自于两种背包对物品选取次数的限制不同，进而影响了状态转移时对“前序状态”的依赖逻辑——而且要澄清一点：0/1背包也能优化成一维数组，只是你观察到的是更基础的二维写法，而完全背包的一维写法刚好贴合它的规则，所以显得更主流。

先聊0/1背包的二维数组逻辑 #

0/1背包的核心规则是每个物品只能选0次或1次，所以我们最初的状态定义会非常清晰：
dp[i][j] 表示「考虑前i个物品，背包容量为j时能获得的最大价值」

状态转移时，对于第i个物品，我们有两种选择：

• 不选它：那当前状态直接继承前i-1个物品在容量j下的结果，即 dp[i][j] = dp[i-1][j]
• 选它：那必须用前i-1个物品在容量j - weight[i]下的结果，加上当前物品的价值，即 dp[i][j] = dp[i-1][j - weight[i]] + value[i]

这里的关键是必须依赖「不包含当前物品」的前序状态（i-1阶段），才能保证每个物品只被选一次。二维数组的写法能直观地把“前i个”和“前i-1个”的状态分开，对初学者来说更容易理解，不会混淆“是否已经选过当前物品”的问题。

如果直接用一维数组dp[j]，如果正向遍历容量j，会出现什么问题？假设我们更新dp[j]时，用到的dp[j - weight[i]]已经是选过第i个物品后的状态，这就导致同一个物品被多次选取，违反了0/1背包的规则——所以早期教学里更倾向于用二维数组来明确状态边界。

再看完全背包的一维数组适配性 #

完全背包的规则是每个物品可以无限次选取，这时候状态转移的逻辑变了：
如果选第i个物品，我们可以依赖「已经考虑过第i个物品」的状态，也就是dp[i][j - weight[i]] + value[i]（注意这里是i而不是i-1），因为选完一次后还能再选这个物品。

这时候把二维数组压缩成一维就非常顺畅了：我们只需要正向遍历背包容量j，这样dp[j] = max(dp[j], dp[j - weight[i]] + value[i])中的dp[j - weight[i]]，已经包含了“之前选过第i个物品”的状态，刚好符合无限选取的需求。这种写法既节省空间，又完全贴合问题逻辑，自然成了完全背包的主流实现方式。

补充：0/1背包也能写一维！ #

其实0/1背包的一维写法也存在，只要反向遍历背包容量j，这样在更新dp[j]时，dp[j - weight[i]]还是「i-1阶段」的未更新状态，就能保证每个物品只被选一次。举个代码例子：

# 0/1背包一维优化写法
def zero_one_knapsack(capacity, weights, values):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # 反向遍历，避免重复选取当前物品
        for j in range(capacity, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[-1]

而完全背包的一维写法则是正向遍历：

# 完全背包一维写法
def unbounded_knapsack(capacity, weights, values):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # 正向遍历，允许重复选取当前物品
        for j in range(w, capacity + 1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[-1]

总结 #

两者数组维度选择的差异，本质是物品选取次数的限制导致状态转移对前序状态的依赖不同：

• 二维数组是更基础的状态表达，能清晰区分不同物品阶段的状态，适合0/1背包教学时明确逻辑；
• 一维数组是空间优化后的写法，完全背包的无限选取规则刚好适配正向遍历的一维逻辑，所以常用一维实现；而0/1背包的一维写法需要反向遍历，教学中常先展示二维版本来降低理解门槛。

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