01 背包问题

问题描述：

给定 n 件物品，物品的重量为 weight[i]，物品的价值为 value[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 W，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

每个动态规划都从一个网格开始

动态规划——二维空间

令dp[i] [k] 表示前i件物品放入容量为k的背包中所获取的最大价值

初始条件：i=0或者k=0,dp[i] [k] 均为0

状态转移方程，对于编号为i的物品：

• 如果选择放入背包，那么当前背包的最大价值为当前第i件物品的价值与减去第i件物品重量后剩余空间所能容纳的最大价值之和，即dp[i-1] [k-weight[i]] + value[i]

• 如果选择不放入背包，那么当前背包的总价值为dp[i-1] [k]

• 所以dp[i] [k]应选择两者的较大值：

  Max(dp[i-1] [k]，dp[i-1] [k-weight[i]]  + value[i]) 
  

代码实现：

public static int backpack(int[] weights, int[] values, int W) {
      if (weights == null || weights.length == 0) return 0;

      int n = weights.length;
      int[][] dp = new int[n + 1][W + 1];
      for (int i = 1; i <= n; i++) {
          for (int k = 1; k <= W; k++) {
              // 存放第i件物品
              dp[i][k] = k >= weights[i - 1] ? dp[i - 1][k - weights[i - 1]] + values[i - 1] : 0;
              // max(存放第i件物品，不存放第i件物品)所能获取的最大价值
              dp[i][k] = Math.max(dp[i][k], dp[i - 1][k]);
          }
      }
      return dp[n][W];
  }

动态规划+压缩空间

从上面代码实现中可看出来，dp[i] [...] 只和dp[i-1] [...]有关，所以没必要使用O(nW)的辅助空间，仅用O(W)的辅助空间

状态转移方程变成dp[k] (新值) = Max( dp[k-weight[i]] + values[i] , dp[k] (旧值))

代码实现

public static int backpack(int[] weights, int[] values, int W) {
    if (weights == null || weights.length == 0) return 0;

    int n = weights.length;
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++) {
        // 索引较小的元素可能会被覆盖,此处需要后往前
        for (int k = W; k >= 1; k--) {
            // 存放第i件物品
            int valueWith_i = k >= weights[i] ? dp[k - weights[i]] + values[i] : 0;
            // 不存放第i件物品
            int valueWithout_i = dp[k];
            // max(存放第i件物品，不存放第i件物品)所能获取的最大价值
            dp[k] = Math.max(valueWith_i, valueWithout_i);
        }
    }
    return dp[W];
}

k < weights[i]时dp[k]=max(dp[k],0)，相当于没有更新，所以可以进行简化，更早结束循环

public static int backpack(int[] weights, int[] values, int W) {
    if (weights == null || weights.length == 0) return 0;

    int n = weights.length;
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++) {
        // 索引较小的元素可能会被覆盖,此处需要后往前
        for (int k = W; k >= weights[i] ; k--) {
            // 存放第i件物品
            int valueWith_i =dp[k - weights[i]] + values[i];
            // 不存放第i件物品
            int valueWithout_i = dp[k];
            // max(存放第i件物品，不存放第i件物品)所能获取的最大价值
            dp[k] = Math.max(valueWith_i, valueWithout_i);
        }
    }
    return dp[W];
}

01 背包问题

原文：https://www.cnblogs.com/fyusac/p/14872109.html