问题

给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 w[i]，价值为 v[i]。现在让你用这个背包装物品，问最多能装的价值是多少？

  1. 示例：
  3. 输入：W = 5, N = 3
  4.      w = [3, 2, 1], v = [5, 2, 3]
  5. 输出：8
  6. 解释：选择 i=0 和 i=2 这两件物品装进背包。它们的总重量 4 小于 W，同时可以获得最大价值 8。

伪代码

  1. /* 
  2.  * tn: traversed n，即已经遍历过的物品；
  3.  * rw: reserved w，即背包还能容量的重量。
  4.  */
  5. DP(int tn, int rw) {
  6.   // 当遍历完所有物品时，就该返回 0 了，因为没有物品也就没有价值了
  7.   if tn < 0
  8.     return 0
  10.   // 当背包还能容纳的重量已经小于当前物品的重量时，显然这个物品不能放入背包
  11.   if rw < w[tn]
  12.     return DP(tn - 1, rw)
  14.   // 作出决策，该不该放入物品：
  15.   //   1. 放入：那么价值是 DP(tn - 1, rw - w[tn])；
  16.   //   2. 不放入：那么价值是 DP(tn - 1, rw)。
  17.   return max(DP(tn - 1, rw), DP(tn - 1, rw - w[tn]) + v[tn])
  18. }

代码实现java版：

  1. public static void main(String[] args) {
  2.     int N = 3, W = 5; // 物品的总数，背包能容纳的总重量
  3.     int[] w = {0, 3, 2, 1}; // 物品的重量
  4.     int[] v = {0, 5, 2, 3}; // 物品的价值
  5.     int dp = dp(w, v, N, W);
  6.     System.out.println(dp);
  7. }
  9. /**
  10.      * @param w 重量数组
  11.      * @param v 价值数组
  12.      * @param N 有多少个可选物品
  13.      * @param W 背包容量
  14.      */
  15. public static int dp(int[] w, int[] v, int N, int W) {
  16.     // 创建备忘录二维表
  17.     int[][] dp = new int[N + 1][W + 1];
  19.     // 遍历每个物品确定是否放入背包
  20.     for (int tn = 1; tn < N + 1; tn++) {
  21.         // 遍历容量，根据策略确定是否放入当前物品
  22.         for (int rw = 1; rw < W + 1; rw++) {
  23.             if (rw < w[tn]) {
  24.                 // 说明放不下当前物品,最优就等于前n-1个物品的存放策略
  25.                 dp[tn][rw] = dp[tn - 1][rw];
  26.             } else {
  27.                 // 根据不存放当前物品，和存放当前物品两种情况，取较大值即为最优
  28.                 int otherW = rw - w[tn];
  29.                 // 前n-1个物品在容量为otherW的情况的较优解
  30.                 int otherVal = dp[tn - 1][otherW];
  31.                 // 取较大值
  32.                 dp[tn][rw] = Math.max(dp[tn - 1][rw], otherVal + v[tn]);
  33.             }
  34.         }
  35.     }
  36.     return dp[N][W];
  37. }

整个状态转移过程

image.png