背包问题本质

背包问题是【动态规划】中十分经典的一类问题，本质上属于组合优化的【NP完全问题】，是一个无法避免【穷举】的问题，同时也满足【无后效性】。
【背包问题】大概对应这样的一类问题：泛指一类【给定价值与成本】，同时【限定决策规则】，在这样的条件下，如何实现价值最大化的问题。

「01背包」是指给定物品价值与体积（对应了「给定价值与成本」），在规定容量下（对应了「限定决策规则」）如何使得所选物品的总价值最大。

题目描述

有N件物品和一个容量为V的背包，每件物品有且只有1件。第i件物品的题只为v[i]，价值为w[i]，求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
image.png

解法：动态规划，dp[N][C+1]

  1. dp数组定义：dp[i][j]：枚举到第i件物品时，剩余容量为j，此时能获得的最大价值
  2. 不失一般性的，我们只需要考虑第 i件物品如何选择即可，对于第 i件物品，我们有「选」和「不选」两种决策。「不选」其实就是 ，等效于我们只考虑前i-1件物品，当前容量为 j的情况下的最大价值。同理，如果我们选第i件物品的话，代表消耗了v[i]的背包容量，获取了w[i]的价值，那么留给前i-1件物品的背包容量就只剩j-v[i] 。即最大价值为dp[i-1][j-v[i]] + w[i]。当然，选第i件有一个前提：「当前剩余的背包容量」>=「物品的体积」。
  3. 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])
    1. class Solution {
    2.  //物品编号从0开始，到N-1一共N件，体积从0到C一共C+1个选择
    3.  public int maxValue(int N, int C, int[] v, int w) {
    4.      int[][] dp = new int[N][C+1]; //res = dp[N-1][C]
    5.      //base case，第一件物品
    6.      for (int i=0; i<=C; i++) {
    7.          dp[0][i] = i >= v[0] ? w[0] : 0;
    8.      }
    9.      //剩余物品
    10.      for (int i=0; i<N; i++){
    11.          for (int j=0; j<C+1; j++) {
    12.              int noChoose = dp[i-1][j]; //
    13.              int Choose = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : 0;
    14.              dp[i][j] = Math.max(noChoose, Choose);
    15.          }
    16.      }
    17.      return dp[N-1][C];
    18.  }
    19. }
    image.png

优化

优化1：
优化2：