一线大厂高级前端编写,前端初中阶面试题,帮助初学者应聘,需要联系微信:javadudu

谈01背包和完全背包

背景

有 n 个物品和容量为 V 的背包,第 i 件物品的体积为 c[i],价值为 w[i]。现在的目标是确定要将哪些物体放入背包,以保证在体积 不超过背包容量 的前提下,背包内的 总价值最高。

其次,基于以上前提条件,通过添加不同的约束条件,就形成了不同的背包问题。

01背包(二维数组)

约束条件:每种物品数量为 1,可以选择放或不放

状态转移方程

状态定义:f[i][v]为前 i 个 物品中,体积恰好为 v 时的最大价值。

result = max(f[n][0 ~ V])即最终答案,它表示前 n个物品的最大价值,假设这时容量为 k ,由于 0 <= k <= V,因此容量要在 0 ~ V求最大值来寻找 k

状态转移方程:

f[i][v] = max(f[i-1][v], f[i-1][v-c[i]] + w[i])

以上得到的状态 i 和状态 i-1 关系是从 实际意义 推断出来的。

  • 如果 不选第 i 个物品,那么前 i 个背包的最大价值就是前 i-1 个物品的价值,即 f[i][v] = f[i-1][v];
  • 如果 选择了第 i 个物品,前 i-1 个物品的体积就是 v-c[i],状态方程为 f[i-1][v-c[i]],注意这时的价值是前 i-1 个物品的价值,因此少了 w[i] 的价值,所以 f[i][v] = f[i-1][v-c[i]] + w[i]。

最后我们要在这两种情况中选择能使物品最大价值更大的那个方案,故取最大值。最终我们就得到了以上的状态转移方程。

代码实现

由于 f[i][v] 是二维的,所以我们可以使用 二维数组 实现,时间复杂度和空间复杂度均为 O(nV)

let f = new Array(n+1).fill(0).map(() => new Array(V+1).fill(0)); // 初始化二维数组全为零

for (let i = 1; i <= n; i++) { // 枚举前i个物品
  for (let v = 0; v <= V; v++) { // 枚举体积
    f[i][v] = f[i-1][v]; // 不选择第i个物品
    if (v >= c[i]) { // 第i个物品的体积必须小于v才能选择
      f[i][v] = Math.max(f[i][v], f[i-1][v-c[i]] + w[i]);
    }
  }
}

let result = Math.max(...f[n]); // 返回前n个物品的最大值
return result;

二维数组又可以优化成如下

let f = new Array(n+1).fill(0).map(() => new Array(V+1).fill(0)); // 初始化二维数组全为零

for (let i = 1; i <= n; i++) { // 枚举前i个物品
  for (let v = c[i]; v <= V; v++) { // 枚举体积
      f[i][v] = Math.max(f[i-1][v], f[i-1][v-c[i]] + w[i]);
  }
}

let result = Math.max(...f[n]); // 返回前n个物品的最大值
return result;

我们甚至可以把i给优化掉。

为什么?

先看看f[i][v]的定义:f[i][v]为前 i 个 物品中,体积恰好为 v 时的最大价值。

我们需要的信息是,所有物品中,背包体积为v的最大值。即f[MAX_COUNT][v]。其中MAX_COUNT为常量,v需要参与动态规划,所以是变动的。

完全背包问题

那么就使用一维数组来实现,但是可使空间复杂度降到 O(V)。

let f = new Array(n+1).fill(0).map(() => new Array(V+1).fill(0)); // 初始化二维数组全为零

for (let i = 1; i <= n; i++) { // 枚举前i个物品
  for (let v = c[i]; v <= V; v++) { // 枚举体积
      f[v] = Math.max(f[v], f[v-c[i]] + w[i]);
  }
}

return f(n)

这段代码看上去ok吗?

其实不ok,因为状态表达式 f[i][v] = Math.max(f[v], f[v-c[i]] + w[i])中,f[v]的值需要用上一轮的f[v-c[i]]的值去更新。

为什么?

因为上一轮迭代记录了i-1个物品在背包不同的体积下的状态,一个物品只能放一次。如果我们使用正序,会出现重复放物品的情况。

让我们举个反例看看:

  • 初始状态:

    • f = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  • i = 1, 第1个物品(体积2,价值3):

    • f = [0, 0, 3, 3, 6, 6, 9, 9, 12, 12, 15]
  • i = 2,第2个物品(体积3,价值4):

    • f = [0, 0, 3, 4, 6, 7, 9, 10, 12, 13, 15]
  • i = 3, 加入第3个物品(体积4,价值5):

    • f = [0, 0, 3, 4, 6, 7, 9, 10, 12, 13, 15]
  • i = 4, 加入第4个物品(体积5,价值6):
    • f = [0, 0, 3, 4, 6, 7, 9, 10, 12, 13, 15]

可以看到,当一轮循环中背包体积变大时,物品会被重复放置。

这个反例其实就是完全背包。

01背包(一维数组)

为了避免重复放置的情况,所以内部循环需要倒序。

let f = new Array(V+1).fill(0); // 初始化一维数组全为零

for (let i = 1; i <= n; i++) { // 枚举前i个物品
  for (let v = V; v >= c[i]; v--) { // 注意这里是倒序遍历
    f[v] = Math.max(f[v], f[v-c[i]] + w[i]);
  }
}
return f(n)

我们试着用一个例子来理解这个一维数组

假设我们有一个背包,其容量为 V为10。我们有4个物品,它们的体积和价值分别如下:

物品: 1 2 3 4
体积: c = [2, 3, 4, 5]
价值: w = [3, 4, 5, 6]

我们逐步分析代码执行结果:

  1. 初始状态:
    • f = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  2. i = 1, 第1个物品(体积2,价值3):
    • f = [0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3]
  3. i = 2, 第2个物品(体积3,价值4):
    • f = [0, 0, 3, 4, 4, 7, 7, 7, 7, 7, 7]
  4. i = 3, 第3个物品(体积4,价值5):
    • f = [0, 0, 3, 4, 5, 7, 8, 9, 9, 12, 12]
  5. i = 4, 第4个物品(体积5,价值6):
    • f = [0, 0, 3, 4, 5, 7, 8, 9, 10, 12, 13]

可以看到:

  • 可以看到,对于第一个物品,只要背包体积够,就会被放入
  • 对于第二个物品,则会根据状态转移式来做决策。

f[v] = Math.max(f[v], f[v-c[i]] + w[i]);

根据这个式子可知,第二个物品可能被放入,也可能不被放入。

f[v]代表第二个物品不被放入。f[v-c[i]]代表第二个物品被放入。

那么第二个物品被放入,背包中的物品会不会被丢弃呢?

首先,由于背包容量越大,背包内可装的东西价值越多。

所以f[v]>=f[v-c[i]]

  • 当f[v] = f[v-c[i]],则不需要丢弃东西持续往背包中装东西。
  • 当f[v] > f[v-c[i]],则表示我们用i物品替换了等体积的物品。我们不知道是哪个物品。但是 max(f[v],f[v-c[i]]+w[i])能保证我们每次的替换都会使背包内的东西价值更高。
  • 那么当我们循环了i次,就用i个物品把背包内的价值替换了一遍,背包内的东西必然就是当前最高价值的。

总结

01背包,是二维的。二维是因为每个物品都只能选一次。可以简化成一维,但是需要反向遍历避免重复增加的情况。完全背包是因为存在重复增加的情况,所以直接用一维正序。

本文参考

leetcode.cn/problems/co…

在leecode刷题时看了这个大佬的文章,理解了背包的基本概念,再加入了自己的想法进行推演。

原文链接:https://juejin.cn/post/7332752948417462287 作者:glbb666

(0)
上一篇 2024年2月9日 下午4:38
下一篇 2024年2月9日 下午4:49

相关推荐

发表评论

登录后才能评论