【DP】01背包与完全背包总结及空间优化

01背包问题

​ 题目描述：有n件物品，每件物品的重量为w[i]，价值为c[i]。现在有一个容量为V的背包，问怎么选取物品放入背包，能使得背包内的总价值最大。其中每件物品只能放入一次。

​ 样例：

n = 5, V =8
w[i] = 3, 5, 1, 2, 2
c[i] = 4, 5, 2, 1, 3

​ 分析：使用暴力的解法，每件物品分为放入、不放入，因此复杂度为O(2^n)。因此考虑使用动态规划的方法，设dp[i][j]表示选择前i件物品，重量恰好为j的最大价值，则易得：

​ dp[i][j] = max { dp[i-1][j], dp[i-1][j-w[i]] + c[i] }

• 不选此物品，则价值最大值为 前i-1件物品、容量j的价值
• 选择此物品，则价值最大值为 前i-1件物品、容量j - 当前物品重量 w[i] 加上当前物品的价值
• 两种情况的最大值即为前i件物品，重量恰好为j的最大价值

二维dp写法

public static void main(String[] args) {
    var w = new int[]{1, 3, 4};
    var v = new int[]{15, 20, 30};
    int n = w.length;
    int V = 4;

    var dp = new int[n][V+1];
    for(int j = w[0]; j <= V; j++) {
        dp[0][j] = v[0];
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= V; j++) {
            if(j-w[i] < 0) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }

    for(var row : dp) {
        System.out.println(Arrays.toString(row));
    }
}

一维滚动数组写法

	public static void main(String[] args) {
        var w = new int[]{1, 3, 4};
        var v = new int[]{15, 20, 30};
        int n = w.length;
        int V = 4;

        var dp = new int[V+1];
        for(int j = w[0]; j <= V; j++) {
            dp[j] = v[0];
        }

        for(int i = 1; i < n; i++) {
            for(int j = V; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
            }
        }

        System.out.println(Arrays.toString(dp));
    }

一维滚动数组的写法只能是倒序：

​ 如果是正序的话，dp[1] = dp[1 - weight[0]] + value[0] = 15

​ dp[2] = dp[2 - weight[0]] + value[0] = 30

​ 即重量为2的dp值使用了重量为1的dp值（这个值已经添加了一次物品），因此为了保证只使用一次物品，要倒序遍历（保证前面的dp值没有更新，即没有添加当前物品）

​ 当然正序的做法也恰好能用于完全背包问题

完全背包问题

​ 题目描述：有n件物品，每件物品的重量为w[i]，价值为c[i]。现在有一个容量为V的背包，问怎么选取物品放入背包，能使得背包内的总价值最大，其中每件物品有无数件。

​ 样例：

n = 5, V =8
w[i] = 3, 5, 1, 2, 2
c[i] = 4, 5, 2, 1, 3

​ 分析：使用暴力的解法，每件物品分为放入、不放入，因此复杂度为O(2^n)。因此考虑使用动态规划的方法，设dp[i][j]表示选择前i件物品，重量恰好为j的最大价值，则易得：

	dp[i][j] = max { dp[i-1][j], dp[i][j-w[i]] + c[i] }

​ 对比01背包问题

	dp[i][j] = max { dp[i-1][j], dp[i-1][j-w[i]] + c[i] }

• 不选此物品，则价值最大值为 前i-1件物品、容量j的价值
• 选择此物品，则价值最大值为 前i件物品（允许再次选择第i件）、容量j - 当前物品重量 w[i] 加上当前物品的价值
• 两种情况的最大值即为前i件物品，重量恰好为j的最大价值

二维dp写法

public static void main(String[] args) {
    var w = new int[]{1, 3, 4};
    var v = new int[]{15, 20, 30};
    int n = w.length;
    int V = 4;

    var dp = new int[n][V+1];
    for(int j = w[0]; j <= V; j++) {
        dp[0][j] = v[0];
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= V; j++) {
            if(j-w[i] < 0) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i]] + v[i]);
            }
        }
    }

    for(var row : dp) {
        System.out.println(Arrays.toString(row));
    }
}