【背包问题系列】一、经典背包问题

经典背包问题

[题目描述]

有**N**件物品和一个容量是**V**的背包。每件物品有且只有一件。
第 件物品的重量是**weights[i]**，价值是**values[i]**。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
示例 1：
输入: V = 4, values = [4,2,3], weights = [4,2,3]
输出: 4
解释: 只选第一件物品，可使价值最大。
示例 2：
输入: V = 5, values = [4,2,3], weights = [4,2,3]
输出: 5
解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。

[思路以及题目分析]

• 面对dp问题我们最开始不能直接想到dp方程的时候，可以考虑通过DFS｜递归来确定递归方程

• 根据本题题目分析可以得出递归方程int dfs(int n,int i, int[] values, int[] weights )

• n（当前容量）、i（当前物品）

• 因此dp方程可以确定由两个可变参数生成

• dp[i][j]表示在使用前i个物品，在最大重量j的情况，获得的最高价值

• 当i = 0时，需要初始化dp数组dp[0][j]

• 动态方程推导可以按照如下思路分析

• 面对i物品是否取值，需要判断取(dp[i][j-weight[i]] + val[i])或者不取(dp[i-1][j])谁的价值更高

• dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weights[i]] + values[i])
  

public int getMaxValue(int[] value, int[] weights, int n) {
            int[][] dp = new int[value.length][n + 1];
            //边界条件
            for (int i = 0; i < n; i++) {
                dp[0][i] = (weights[0] <= i) ? value[0] : 0;
            }
            for (int i = 1; i < value.length; i++) {
                int val = value[i];
                for (int j = 1; j <= n; j++) {
                    if (j >= weights[i]) {
                        //取选当前物品和不选当前物品的最大值
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + val);
                    }
                }
            }
            return dp[value.length - 1][n];
        }

**时间复杂度O(NC) N代表物品数量，C代表最大重量

优化一：滚动数组以及动态规划的结合优化存储空间

• 根据上述递归方程可以看到dp[i][j]只和dp[i-1][j]有关，这样的动态规划问题可以通过滚动数组来进行dp方程求解
• 定义dp[2][j]存储前一位的最大价值求解和当前位最大价值求解
• 至于如何遍历两个元素我们可以通过奇偶性来平移遍历

 public int getMaxValue(int[] values, int[] weights, int n) {
            int[][] dp = new int[2][n + 1];
            for (int i = 0; i < n; i++) {
                dp[0][i] = (weights[0] <= i) ? values[0] : 0;
            }
            for (int i = 1; i < values.length; i++) {
                for (int j = 0; j <= n; j++) {
                    //不选择当前物品
                    int tempF = dp[(i - 1) & 1][j];
                    //选择当前物品
                    int tempT = j >= weights[i] ? dp[(i - 1) & 1][j - weights[i]] + values[i] : 0;
                    dp[i & 1][j] = Math.max(tempF, tempT);
                }
            }
            return dp[(values.length - 1) & 1][n];
        }

**时间复杂度O(NC) N代表物品数量，C代表最大重量

优化二：明确依赖关系，再度进行空间优化

• 根据上述优化可以发现，当前的最大价值仅与两个确定的值有关
• 也就是dp[i][j]仅与dp[i-1][j] 和dp[i][j-weights[i]]两个值
• 

public int getMaxValue(int[] values, int[] weights, int n) {
            int[] dp = new int[n + 1];
            for (int i = 0; i < values.length; i++) {
                for (int j = n; j >= weights[i]; j--) {
                    // 不选该物品
                    int x = dp[j];
                    // 选择该物品
                    int y = dp[j - weights[i]] + values[i];
                    dp[j] = Math.max(x, y);
                }
            }
            return dp[n];
        }