0-1 背包问题

1 贪心

假设一个背包可以装 100 kg 物品，我们有如下 5 种豆子，每种豆子的总量和总价值各不相同，为了让背包中所装的物品总价值最大，我们如何选择在背包中装哪些豆子，每种豆子该装多少？

物品	总量（kg）	总价值（元）
黄豆	100	100
绿豆	30	90
红豆	60	120
黑豆	20	80
青豆	50	75

思路：先对数据进行排序，先装单价高的，装到不能装为止。

bag01_1.js

function bag01_1(max, beans) {
  const value = [];
  let rest = max;
  const res = [];
  for (let i = 0; i < beans.length; i++) {
    value.push([i, beans[i][2] / beans[i][1]]);
  }
  value.sort((a, b) => b[1] - a[1]);

  for (let i = 0; i < value.length; i++) {
    const weight = beans[value[i][0]][1];
    const type = beans[value[i][0]][0];
    const val = value[i][1];
    if (weight < rest) {
      rest = rest - weight;
      res.push([type, weight, val]);
    } else {
      res.push([type, rest, val]);
      break;
    }
  }
  return res;
}

module.exports = bag01_1;

bag01_1.test.js

const bag01_1 = require('../src/bag01_1');

test('leetcode1', () => {
  expect(bag01_1(100, [['黄豆', 100, 100], ['绿豆', 30, 90], ['红豆', 60, 120], ['黑豆', 20, 80], ['青豆', 50, 75]]))
  .toStrictEqual([['黑豆', 20, 4], ['绿豆', 30, 3], ['红豆', 50, 2]]);
});

2 回溯

我们有一个背包，背包总的承载重量是 W kg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

注意：这里的不可分割，代表着我们是不能像上一题那样去计算单价。

显然，这个问题已经无法通过贪心算法来解决了（因为如果每次都取最值钱并不能保证总价值最高）。但是用回溯算法可以解决。

思路：对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于 n 个物品来说，总的装法就有 2^n 种，去掉总重量超过 W kg 的，从剩下的装法中选择总重量最接近 W kg 的。2^n 种装法不重复地枚举出来，可以使用回溯。

我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。

使用一点搜索剪枝的技巧，就是当发现已经选择的物品的重量超过 W kg 之后，我们就停止继续探测剩下的物品，这样可以有一定提速。

bag01_2.js

function bag01_2(max, n, items) {
  //存储背包中物品总重量的最大值
  let maxW = 0;
  f(0, 0, items, n, max);
  return maxW;
  // cw表示当前已经装进去的物品的重量和
  // i表示考察到哪个物品了
  // w背包重量
  // items表示每个物品的重量
  // n表示物品个数
  // 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
  // f(0, 0, a, 10, 100)
  function f(i, cw, items, n, w) {
    if (cw === w || i === n) { // cw === w表示装满了;i === n表示已经考察完所有的物品
      if (cw > maxW) maxW = cw;
      return;
    }
    f(i + 1, cw, items, n, w); // 不装第 i + 1 个物品的情况
    if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
      f(i + 1, cw + items[i], items, n, w); // 装第 i + 1 个物品的情况
    }
  }
}

module.exports = bag01_2;

bag01_2.test.js

const bag01_2 = require('../src/bag01_2');

test('bag01_2', () => {
  expect(bag01_2(100, 10, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10])).toBe(100);
  expect(bag01_2(100, 10, [110, 200, 10, 80, 10, 10, 10, 50, 20, 30])).toBe(100);
  expect(bag01_2(100, 10, [110, 200, 101, 80, 95, 120, 130, 150, 220, 130])).toBe(95);
  expect(bag01_2(100, 10, [110, 200, 101, 20, 15, 120, 37, 50, 220, 130])).toBe(87);
  expect(bag01_2(9, 5, [2, 2, 4, 6, 3])).toBe(9);
});

题目难度升级

上述背包问题，只涉及背包重量和物品重量。现在需要引入物品价值，对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少？

bag01_5.js

function bag01_5(w, n, items, values) {
  //存储背包中物品总价值的最大值
  let maxV = 0;
  f(0, 0, 0);
  return maxV;
  // cw表示当前已经装进去的物品的重量和
  // cv表示当前已经装进去的物品的价值和
  // i表示考察到哪个物品了
  function f(i, cw, cv) {
    if (cw === w || i === n) { // cw === w表示装满了;i === n表示已经考察完所有的物品
      if (cv > maxV) maxV = cv;
      return;
    }
    f(i + 1, cw, cv); // 不装第 i + 1 个物品的情况
    if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
      f(i + 1, cw + items[i], cv + values[i]); // 装第 i + 1 个物品的情况
    }
  }
}

module.exports = bag01_5;

bag01_5.test.js

const bag01_5 = require('../src/bag01_5');

test('bag01_5', () => {
  expect(bag01_5(9, 5, [2, 2, 4, 6, 3], [3, 4, 8, 9, 6])).toBe(18);
});

3 动态规划

题目要求与题目2相同，回溯算法的时间复杂度是指数级别的O(2^n)，为了降低时间复杂度，可以使用动态规划来解决这个问题。

思路：我们把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。

我们把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量），也就是例子中的 9。于是，我们就成功避免了每层状态个数的指数级增长。

我们用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态。

第 0 个（下标从 0 开始编号）物品的重量是 2，要么装入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是 0 或者 2。我们用 states[0][0]=true 和 states[0][2]=true 来表示这两种状态。

第 1 个物品的重量也是 2，基于之前的背包状态，在这个物品决策完之后，不同的状态有 3 个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用 states[1][0]=true，states[1][2]=true，states[1][4]=true 来表示这三种状态。

我们只需要在最后一层，找一个值为 true 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值。

bag01_3.js

function bag01_3(max, n, items) {
  // 初始化一个二维数组用来记录每个阶段的状态
  const states = [];
  for (let i = 0; i < n; i++) {
    states.push([]);
    for (let j = 0; j < max + 1; j++) {
      states[i].push(false);
    }
  }
  // 第一行数据特殊处理
  states[0][0] = true;
  if (items[0] < max) {
    states[0][items[0]] = true;
  }
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < max + 1; j++) {
      if (states[i - 1][j] === true) { // 不把第i个物品放入背包
        states[i][j] = states[i - 1][j];
      }
      if (states[i - 1][j] && j + items[i] <= max) { // 把第i个物品放入背包
        states[i][j + items[i]] = true;
      }
    }
  }
  for (let i = max; i >= 0; i--) {
    if (states[n - 1][i]) {
      return i;
    }
  }
}

module.exports = bag01_3;

bag01_3.test.js

const bag01_3 = require('../src/bag01_3');

test('bag01_3', () => {
  expect(bag01_3(100, 10, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10])).toBe(100);
  expect(bag01_3(100, 10, [110, 200, 10, 80, 10, 10, 10, 50, 20, 30])).toBe(100);
  expect(bag01_3(100, 10, [110, 200, 101, 80, 95, 120, 130, 150, 220, 130])).toBe(95);
  expect(bag01_3(100, 10, [110, 200, 101, 20, 15, 120, 37, 50, 220, 130])).toBe(87);
  expect(bag01_3(9, 5, [2, 2, 4, 6, 3])).toBe(9);
});

这个方法的时间复杂度是O(n*w)，n 表示物品个数，w 表示背包可以承载的总重量。

空间复杂度优化

空间复杂度方面，需要额外申请一个 n 乘以 w+1 的二维数组，对空间的消耗比较多。实际上，我们只需要一个大小为 w+1 的一维数组就可以解决这个问题。动态规划状态转移的过程，都可以基于这个一维数组来操作。

bag01_4.js

function bag01_4(max, n, items) {
  // 初始化一个数组用来记录状态，每个阶段共用一个数组
  const states = [];
  for (let j = 0; j < max + 1; j++) {
    states.push(false);
  }
  // 第一层数据特殊处理
  states[0] = true;
  if (items[0] < max) {
    states[items[0]] = true;
  }
  for (let i = 1; i < n; i++) {
    for (let j = max; j >= 0; j--) { // j 需要从大到小来处理，如果我们按照 j 从小到大处理的话，会出现 for 循环重复计算的问题
      if (states[j] && j + items[i] <= max) { // 把第i个物品放入背包
        states[j + items[i]] = true;
      }
    }
  }
  for (let i = max; i >= 0; i--) {
    if (states[i]) {
      return i;
    }
  }
}

module.exports = bag01_4;

bag01_4.test.js

const bag01_4 = require('../src/bag01_4');

test('bag01_4', () => {
  expect(bag01_4(100, 10, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10])).toBe(100);
  expect(bag01_4(100, 10, [110, 200, 10, 80, 10, 10, 10, 50, 20, 30])).toBe(100);
  expect(bag01_4(100, 10, [110, 200, 101, 80, 95, 120, 130, 150, 220, 130])).toBe(95);
  expect(bag01_4(100, 10, [110, 200, 101, 20, 15, 120, 37, 50, 220, 130])).toBe(87);
  expect(bag01_4(9, 5, [2, 2, 4, 6, 3])).toBe(9);
});

题目难度升级

bag01_6.js

function bag01_6(max, n, items, values) {
  // 初始化一个数组用来记录状态，每个阶段共用一个数组
  const states = [];
  for (let j = 0; j < max + 1; j++) {
    states.push(-1);
  }
  // 第一层数据特殊处理
  states[0] = 0;
  if (items[0] < max) {
    states[items[0]] = values[0];
  }
  for (let i = 1; i < n; i++) {
    for (let j = max; j >= 0; j--) { // j 需要从大到小来处理，如果我们按照 j 从小到大处理的话，会出现 for 循环重复计算的问题
      if (states[j] >= 0 && j + items[i] <= max) { // 把第i个物品放入背包
        v = states[j] + values[i];
        if (v > states[j + items[i]]) {
          states[j + items[i]] = v;
        }
      }
    }
  }
  return Math.max(...states);
}

module.exports = bag01_6;

bag01_6.test.js

const bag01_6 = require('../src/bag01_6');

test('bag01_6', () => {
  expect(bag01_6(9, 5, [2, 2, 4, 6, 3], [3, 4, 8, 9, 6])).toBe(18);
});

0-1 背包问题 ​

1 贪心 ​

2 回溯 ​

题目难度升级 ​

3 动态规划 ​

空间复杂度优化 ​

题目难度升级 ​

0-1 背包问题

1 贪心

2 回溯

题目难度升级

3 动态规划

空间复杂度优化

题目难度升级