如何优化自底向上Knapsack动态规划解法的空间复杂度

原实现使用(n+1)*(c+1)的二维数组存储所有状态，空间复杂度为O(nc)，优化的核心来自对状态转移依赖关系的观察：

计算第i轮（考虑前i个物品）的所有状态值时，仅会用到第i-1轮（考虑前i-1个物品）的结果，更早轮次的状态值完全不会被访问，因此不需要存储全量二维表。

最优优化（仅求最大价值场景） #

可以直接把二维dp数组压缩为长度为c+1的一维数组，空间复杂度直接降到O(c)，且时间复杂度和原实现完全一致，没有额外开销。

实现要点 #

• 一维数组初始值全为0，对应原实现中i=0（不选任何物品）时所有容量下的价值都是0的初始状态
• 遍历每个物品时，将容量的遍历顺序从正序改为倒序：从最大容量c开始，遍历到当前物品的重量wt[i-1]即可（小于该重量的容量无法装下当前物品，值不需要修改，直接继承上一轮结果）
• 倒序遍历的核心作用：保证计算容量j的状态时，用到的j-wt[i-1]位置的值还停留在上一轮（未选当前物品）的状态，不会被当前轮次的计算覆盖，避免出现物品被重复选取的完全背包逻辑。

优化后的代码实现 #

int val[] = new int[] { 60, 100, 120 };
int wt[] = new int[] { 10, 20, 30 };
int capacity= 50; // 背包容量
int n = val.length;
System.out.println(knapsack(capacity, wt, val, n)); // 输出220

public static int knapsack(int c, int wt[], int val[], int n) {
    // 仅开一维dp数组
    int dp[] = new int[c+1];
    
    for(int i = 1; i < n+1; i++) {
        // 倒序遍历容量，到当前物品重量为止
        for(int j = c; j >= wt[i-1]; j--) {
            dp[j] = Math.max(
                val[i-1] + dp[j - wt[i-1]], // 选当前物品的情况
                dp[j] // 不选当前物品的情况，对应原二维dp[i-1][j]
            );
        }
    }
    return dp[c];
}

适配回溯场景的优化方案 #

如果除了最大价值，还需要回溯求出具体选中的物品组合，一维压缩方案会覆盖历史状态无法回溯，这时候可以用滚动二维数组的方案：只开2行int dp[][] = new int[2][c+1]，计算时交替用两行存储当前轮和上一轮的状态，空间复杂度同样是O(c)，同时保留了上一轮的完整状态用于路径回溯。

内容的提问来源于stack exchange，提问作者Pale Blue Dot