问题

给你一个可放总重量为 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. 输出：15
  6. 解释：当 i = 2 时，选取 5 次，总价值为 5 * 3 = 15。

算法问题分析

不同于 0-1 背包问题（每件物品只能拿一次），在完全背包问题中，每件物品可以拿任意多件，只要背包装得下就行。

如果从每件物品的角度来看，与之相关的决策已经不再是选拿（1）或者不拿（0）了；而是拿 0 件、拿 1 件、拿 2 件……直到拿到 (W/w[i]) 件物品为止。

状态转移方程

image.png
代码实现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];
  18.     //
  19.     for (int tn = 1; tn < N + 1; tn++) {
  20.         for (int rw = 1; rw < W + 1; rw++) {
  21.             //
  22.             if (rw < w[tn]) {
  23.                 // 不选
  24.                 dp[tn][rw] = dp[tn - 1][rw];
  25.             } else {
  26.                 int maxNum = rw / w[tn];
  27.                 for (int k = 0; k <= maxNum; k++) {
  28.                     // 前n-1种物品的剩余可装量
  29.                     int otherW = rw - k * w[tn];
  30.                     dp[tn][rw] = Math.max(dp[tn][rw], dp[tn - 1][otherW] + k * v[tn]);
  31.                 }
  32.             }
  33.         }
  34.     }
  35.     return dp[N][W];
  36. }

输出

15

状态转移过程

image.png

时间复杂度优化

如果我们认真分析上面的代码，就可以发现代码中使用了三重循环：

  1. 首先是遍历物品；
  2. 然后是遍历剩余容量；
  3. 最后是遍历物品数量。

那么这个解法的算法时间复杂度是多少呢？如果我们假定物品数量是 k，容量是 v，那么最后的时间复杂度就是 O(kv²)。

改进代码的时间复杂度

我们查看上一份代码不难看出，对于第tn个物品，其rw=0,1,2,3….W，前每个列都要遍历多遍，这属于重复子问题，我们就可以将其转为0-1背包问题，不管前面已经使用了tn这个物品几次，只关心当前容量这一次是否需要放进去即可。

  2. /**
  3.      * @param w 重量数组
  4.      * @param v 价值数组
  5.      * @param N 有多少个可选物品
  6.      * @param W 背包容量
  7.      */
  8. public static int dp(int[] w, int[] v, int N, int W) {
  9.     // 创建备忘录
  10.     int[][] dp = new int[N + 1][W + 1];
  11.     //
  12.     for (int tn = 1; tn < N + 1; tn++) {
  13.         for (int rw = 1; rw < W + 1; rw++) {
  14.             //
  15.             if (rw < w[tn]) {
  16.                 // 不选
  17.                 dp[tn][rw] = dp[tn - 1][rw];
  18.             } else {
  19.                 dp[tn][rw] = Math.max(dp[tn][rw], dp[tn][rw - w[tn]] + v[tn]);
  20.             }
  21.         }
  22.     }
  23.     return dp[N][W];
  24. }

其得到的状态转移过程一致