常见背包问题——01背包和完全背包

背包问题是动态规划最经典的一个例题。背包问题又分为01背包，完全背包，多重背包等，面试种常见的就是01背包问题和完全背包问题。

在我们开发面试中，最常见的两种背包问题就是01背包和完全背包。所以我们这篇文章推导加实现再加优化以上这两种背包问题。

0/1背包问题

我们来看一下01背包问题：

有N件物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每 件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥物品价值总和最⼤
复制代码

我们先来一组用例：

W=10 N=4 wights=[2,3,4,7] values=[1,3,5,9]
复制代码

首先我们分析一下动态规划的dp[i][j],我们先使用二维数组来表示可以比较清晰一点，它的含义就是在0-i个 物品中取物品的价值总和放进容量为j的背包里的价值的最大总和。

根据上面这句话我们就可以确立二维数据的含义，没错，i表示的就是我们物品个数，j表示的就是我们的背包容量。明确了这一点以后我们来打表观察以下这个数据。

我们可以发现我们本元素总是由它上面的元素与由dp[i - 1][j - wights[i - 1]] + values[i - 1]决定。

并且我们初始化时也应该从0开始。

接着我们可以很容易的写出js代码：

  function PackageTest(M, N, wights, values) {
    let dp = new Array(N + 1).fill(0).map(() => new Array(M + 1).fill(0))
    for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
        if (j < wights[i - 1]) {
          dp[i][j] = dp[i - 1][j]
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wights[i - 1]] + values[i - 1])
        }
      }
    }
    console.log(dp)
    return dp[N][M]
  }
复制代码

滚动数组的优化：

这种方法是将我们的二维数组降为一维数组，如何将二维数组降为一维呢，我们可以观察上面的数据，我们会发现，我们总是依赖上一行的数据，所以我们就可以摒弃这本行的数据，直接在上一行的基础上进行计算，但是需要注意的是，我们需要依赖的数据在我们上一层当前元素位置的前面，所以我们就不能顺序遍历数组了，因为顺序遍历数组会改变我们需要的“dp[j – wights[i – 1]]`值。因此我们选择逆序进行遍历。

所以我们可以写出Js代码：

 function PackageTestTwo(M, N, wights, values) {
    let dp = new Array(M + 1).fill(0)
    for (let i = 1; i <= N; i++) {
      for (let j = M; j >= 1; j--) {
        if (j >= wights[i - 1]) {
          dp[j] = Math.max(dp[j], dp[j - wights[i - 1]] + values[i - 1])
        }
      }
    }
  }
复制代码

以上就是01背包的求解过程。我更推荐第二种滚动数据的方式，因为效率更高，但是理解第二种方式的基础是理解第一种求解方式。

完全背包问题

题目：

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
复制代码

我们分析以下发现和01背包的区别就是，一件商品可以出现多次，而01背包只能出现一次。所以目标明确后，我们继续打表确定动规方式。

首先我们依然还是选用dp[i][j]，它的含义和01背包的dp含义相同。

推导以下：

我们发现和01不同的是，我们当前元素依赖的是上一层同位置的元素和本行的背包剩余元素。

所以我们确立递推公式如上所写。

最终写出JavaScript代码:

  function PerfectPacage(M, N, wights, values) {
    let dp = new Array(N + 1).fill(0).map(() => new Array(M + 1).fill(0))
    for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
        if (j < wights[i - 1]) {
          dp[i][j] = dp[i - 1][j]
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - wights[i - 1]] + values[i - 1])
        }
      }
    }
    return dp[N][M]
  }
复制代码

滚动数组优化：

和01相似，我们依然将二维降一维。但是本次我们不同的是，我们不再依赖本元素位置上一层的数据了，我们使用本层背包剩余位置的数据，所以我们是后者依赖前者，前者又依赖前面元素，所以我们使用顺序遍历。

再来缕一缕我们01为什么是逆序，因为01本层元素是要依赖上层之前位置的元素，如果我们使用一维数组顺序进行遍历，那这个数据早就被改变了，上一组的元素从我们开始循环时就逐步消失了。

递推公式为： dp[j] = Math.max(dp[j], dp[j - wights[i - 1]] + values[i - 1])

代码实现：

  function PerfectPacage2(M, N, wights, values) {
    let dp = new Array(M + 1).fill(0);
    for (let i = 1; i <= N; i++) {
      for (let j =1; j <= M; j++) {
        if (j >= wights[i - 1]) {
        dp[j] = Math.max(dp[j], dp[j - wights[i - 1]] + values[i - 1])
        }
      }
      console.log(dp)
    }
    return dp[M]
  }
复制代码

可以继续做一层判断的优化，内层循环直接从wight[i-1]处开始，因为之前的都是不符合条件的，或者说是元素不需要进行调整的。

  function PerfectPacage2(M, N, wights, values) {
    let dp = new Array(M + 1).fill(0);
    for (let i = 1; i <= N; i++) {
      for (let j = wights[i - 1]; j <= M; j++) {
        dp[j] = Math.max(dp[j], dp[j - wights[i - 1]] + values[i - 1])
      }
      console.log(dp)
    }
    return dp[M]
  }

复制代码