有一个背包，背包的最大承重为 W，还有 N 个物品，每个物品有两个属性：重量和价值，每个物品只有一件。
现在需要选择一些物品装入背包，在不超过背包最大承重的前提下，应该尽量使得装入背包的物品的价值总和最大，求最大价值总和是多少。

输入格式：

第 1 行只有一个整数，表示背包的最大承重；
第 2 行是每个物品重量列表 weights ，使用空格隔开；
第 3 行是第 2 行每个物品对应的价值列表 values，使用空格隔开。
输出格式：

输出一个整数，表示最大价值总和。

输入：
5
4 3 1 1
300 200 150 200
输出：550

解释：背包最大承重为 5，可以选择第 2 个物品、 第 3 个物品、第 4 个物品装入背包，总重量为 3 + 1 + 1 = 5，总价值最大，为 200 + 150 + 200 = 550。

提示：
1 <= W <= 100；
1 <= N <= 100；
1 <= weights[i] <= 1000；
1 <= values[i] <= 1000。

解题思路

比较的思想：

  1. 「0-1 背包」问题的「动态规划」算法正是基于

  2. 一个一个添加物品，重量一个单位一个单位增加，每一次考虑一个物品（在所有背包承重下），比较「选它」和「不选它」两种方案，哪个结果更好

    第一步：定义状态

  3. 集合：满足条件（下标区间范围是 [0..i] 内的所有物品，总重量不超过j）的所有情况

  4. dp(i, j)：上面集合中最大价值

    第二步：状态转移

  5. 对于下标为 i 的物品，有「选」和「不选」两种方案，比较这两种方案选出更好的

    1. 下标为 **i** 的物品没有被选择时：问题转化成求物品的下标区间 [0.. i - 1] 里，选出重量总和不超过 j 的最大价值总和
      1. 上一行同列单元格的值 ：f(i - 1, j)
    2. 下标为 **i** 的物品被选择时：则问题转化成求物品的下标区间[0.. i - 1]里，选出重量总和不超过j - w[i]的最大价值总和，即 dp[i - 1][j - w[i]] + v[i] 为所求，这里i >= 1，并且j - w[i] >= 0 即 w[i] <= j ，也就是说，下标为 i 的物品的重量 w(i) 要 小于等于 当前考虑的背包承重 j ，状态转移才能发生
      1. 当前商品的价值+剩余空间的价值 ： v[i] + dp ( i-1, j - w[i] )

dfdf.pptx 01-背包问题 - 图1

正常写法

  1. dp数组初始化
    1. 状态定义
      1. dp[i][j] 是可供选择前 i 个商品，背包承重为 j 的情况下能够装下的最大价值
    2. 方法
      1. new Array
      2. fill
      3. map
    3. 行
      1. **numOfGoods** 是商品数量，注意初始化后行范围是 [0~numOfGoods - 1]
    4. 列：
      1. maxWeight + 1 背包承重，这里加一是因为要从 0 算起一直到 maxWeight 承重范围的背包，如果是maxWeight那就是[0, maxWeight-1]少算了一个
  2. 初始化
    1. 由于后面递推里需要前一行的东西，那么我们必须初始化第一行，否则直接用第一行就没法获得前一行的数据（根本没有前一行）
    2. 将第一个商品尝试装入所有承重大小的背包
    3. 当前背包装得下，dp[0][j]就更新为第一个商品的价值

  3. 递推

    1. 先遍历行numOfGoods 商品
    2. 对于 ```javascript const backpack01 = function backpack01(maxWeight, weights, values) { const numOfGoods = values.length; if (numOfGoods === 0) return 0;

    // 行 为商品的种类，列是重量 // 这里 maxWeight要+1是为了从 0 算起一直到 maxWeight 承重范围的背包， // 如果是maxWeight那就是[0, maxWeight-1]少算了一个 const dp = new Array(numOfGoods).fill(0).map(() => new Array(maxWeight + 1).fill(0));

    // 初始化第一行 // 每次都增加可以选的商品，目前只能选第一种商品 // 背包maxWeight为0的时候啥都装不下，不需要考虑 for (let i = 1; i <= maxWeight; i++) { // 第一个商品尝试装入所有容量的背包 if (weights[0] <= i) { dp[0][i] = values[0]; } }

    for (let i = 1; i < numOfGoods; i++) { for (let j = 1; j <= maxWeight; j++) {

    // 当前商品重量过大，装不了，那就 if (weights[i] > j) {

    1.  dp[i][j] = dp[i - 1][j];

    } // 装得下,那就比较装和不装的价值大小 else {

    1.  // 不装： 当前商品不选择的价值
    2.  // 装了： 当前商品不选择，并且减去当前商品重量的对应的背包重量的最大价值，在加上当前商品 = 选择当前商品的最大价值
    3.  dp[i][j] = Math.max(dp[i- 1][j], dp[i - 1][j - weight[i]] + values[i])

    } } } // 数组初始化的时候用numOfGoods，生成的数组下标范围是[0, numsOfGoods - 1] return dp[numOfGoods - 1][maxWeight]; } ```

    简化初始化(下标书写麻烦不推荐)

    说明：观察状态转移方程，下标为i的行参考了下标为 i - 1 的行的状态值。为了让 i - 1 >= 0，下标为 0 的行需要初始化。事实上，可以将状态二维数组多设置一行，表示 添加了一个重量为 0、价值为 0 的物品，计算结果与原问题等价

下面的「参考代码 2」给出了示例代码。事实上，这样处理「初始化」的思路我们不是第一次见到了。在编码时，需要注意处理下标偏移等细节

  2. /**
  3.  * @description: 
  4.  * @param {number} W 背包大小
  5.  * @param {number[]} weights 商品重量数组
  6.  * @param {number[]} values 商品价值数组
  7.  * @return {number} 能装入商品的最大价值
  8.  */
  9. const backpack01 = function backpack01(W, weights, values) {
  10.   // N为商品个数
  11.   const N = weights.length;
  12.   if (N === 0) return 0;
  14.   // N+1 是为了添加一个重量为 0、价值为 0 的物品
  15.   // W+1 是为了从 0 算起一直到 W承重范围的背包，如果是W那就是[0, W-1]少算了一个
  16.   const dp = new Array(N + 1).fill(0).map(() => new Array(W + 1).fill(0));
  18.   // N个物品，所以从1开始
  19.   // 添加一个商品，导致后面使用的时候要-1
  20.   for (let i = 1; i <= N; i++) {
  21.     // W可以从 1 开始因为为0啥都装不了，没意义
  22.     for (let j = 1; j <= W; j++) {
  23.       // 当前背包装不下第 i 个物品，则价值就是 i - 1
  24.       if(weights[i - 1] > j){
  25.           dp[i][j] = dp[i - 1][j];
  26.       }
  27.       // 装得下，那就比较装它价值能否更大
  28.       else {
  29.         dp[i][j] = Math.max(dp[i - 1][j], 
  30.                             dp[i - 1][j - weights[i - 1]] + values[i - 1]);
  31.       }
  32.     }
  33.   }
  34.   return dp[N][W];
  35. }