背包问题(01背包问题例题讲解)

背包问题(01背包问题例题讲解)2021-04-07 18:30·人民邮电出版社

无论是Facebook、Google、Microsoft,还是百度、阿里、腾讯……每年大厂面试时总会考察动态规划问题。而作为动态规划类问题中非常重要的一个类别——背包问题,慢慢地走到了舞台中央成为面试高频题中的“佼佼者”。

背包问题(01背包问题例题讲解)

背包问题的一个例子:应该选择哪些盒子,才能使价格尽可能地大,而保持重量小于或等于15 kg?图片源自:维基百科-背包问题

随着面试算法岗位的人数不断增多,背包问题也不像当初那样“天真无邪”,如今也是 “套路” 满满。0-1背包,多重背包,完全背包等背包问题,经历大厂面试官变题型、换表达、改套路之后,让无数面试者短时间内无法找到问题需求,内心os“这题想干嘛?”。很多人都在背包问题上,跪了......

背包问题(01背包问题例题讲解)

图片源自:谷歌图片搞笑表情包

背包问题看起来是个简单的数学问题,但背后的算法逻辑相当复杂,短时间分析不出来,基本上就凉凉了。很多人在面试过程中可能就是因为没有做出一道背包问题,而被大厂拒之门外。如何才能快速掌握背包问题的解题套路,成为大厂offer收割机呢?

跟人邮君一起快速掌握“背包问题”解题技巧,go!

趣学算法(异步图书出品)¥77.4购买

什么背包问题?

背包问题(Knapsack problem)是一种组合优化的NP完全问题。

问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。

相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V。

背包问题有哪些?

背包问题分为以下五种:

  1. 0-1背包问题

  2. 多重背包问题

  3. 完全背包问题

  4. 分组背包问题

  5. 混合背包问题

学习背包问题有什么作用?

背包问题是互联网公司最常见的算法面试题,由于其代码量较小而思维量较大的特点而深受面试官的钟爱。此外,背包问题是学习动态规划的基础,是动态规划入门阶段必须要熟练掌握的问题。这也是为什么背包问题日渐成为大厂面试高频题中的“佼佼者”的原因所在。熟练掌握0-1 背包,多重背包,完全背包等背包问题的解法,可以加深初学者对于动态规划中状态的理解。

0-1背包问题

问题描述

给定n个物品的权重和值,将这些物品放在容量为W的背包中,以在背包中获得最大的总价值。换句话说,给定两个整数数组value[0..n-1]和weight[0..n-1],它们分别表示与n个项目相关联的值和权重。还给定代表背包容量的整数W,找出val[]的最大值子集,以使该子集的权重之和小于或等于W。本题中value[]={60,100,120},weight[]={10,20,30},

W=50。

解题方法

方法1:通过蛮力算法或穷举搜索进行递归。

方法:一种简单的解决方案是考虑所有项目子集,并计算所有子集的总重量和价值。仅考虑总权重小于W的子集。从所有此类子集中,选择最大值子集。

最佳子结构:要考虑项目的所有子集,每个项目可能有两种情况。

  1. 情况1:该项目包含在最佳子集中。

  2. 情况2:该商品未包含在最佳组合中。

因此,可以从n个项目中获得的最大值是以下两个值中的最大值。

  1. 通过n-1个项和W权重(不包括第n个项)获得的最大值。

  2. 第n个项目的值加上n-1个项目获得的最大值,W减去第n个项目(包括第n个项目)的权重。

如果第n个项目的权重大于 W,则第n个项目不能包括在内,情况1是唯一的可能性。

下面是上述方法的python代码实现

def knapSack(W, wt, val, n):    # Base Case      if n == 0 or W == 0:          return 0    # If weight of the nth item is    # more than Knapsack of capacity W,    # then this item cannot be included    # in the optimal solution      if (wt[n-1] > W):          return knapSack(W, wt, val, n-1)    # return the maximum of two cases:    # (1) nth item included    # (2) not included      else:          return max(              val[n-1] + knapSack(                  W-wt[n-1], wt, val, n-1),              knapSack(W, wt, val, n-1))# end of function knapSack#Driver Codeval = [60, 100, 120]wt = [10, 20, 30]W = 50n = len(val)print knapSack(W, wt, val, n)

复杂度分析

  • 时间复杂度: O( 背包问题(01背包问题例题讲解) )。

由于存在多余的子问题。

  • 辅助空间: O(1)。

由于没有额外的数据结构用于存储值。

方法2:通过自下而上的方式构造临时数组K[][],可以避免重新计算相同子问题。

方法:在动态编程中,我们将考虑与递归方法中提到的情况相同的情况。在DP[][]表中,让我们将从1到W的所有可能的权重视为列,并将权重保留为行。考虑到从1到第i的所有值,状态DP[i][j]将表示j-weight的最大值。因此,如果我们考虑wi(ith行中的权重),则可以将其填充到weight value> wi的所有列中。

现在可以发生两种可能性:

  • 在给定的列中填写wi。

  • 不要在给定的列中填写wi。

现在,我们必须最大限度地考虑这两种可能性,形式上,如果我们不在jth列中填充ith权重,则DP[i][j]状态将与DP[i-1][j]相同,但是如果我们填充权重,则DP[i][j]将等于wi的值+上一行中权重为j-wi的列的值。因此,我们将这两种可能性中的最大值用于填充当前状态。

下面是上述方法的python代码实现:

def knapSack(W, wt, val, n):      K = [[0 for x in range(W + 1)] for x in range(n + 1)]      # Build table K[][] in bottom up manner      for i in range(n + 1):          for w in range(W + 1):              if i == 0 or w == 0:                  K[i][w] = 0              elif wt[i-1] <= w:                  K[i][w] = max(val[i-1]                            + K[i-1][w-wt[i-1]],                                 K[i-1][w])              else:                  K[i][w] = K[i-1][w]         return K[n][W]# Driver codeval = [60, 100, 120]wt = [10, 20, 30]W = 50n = len(val)print(knapSack(W, wt, val, n))

复杂度分析

  • 时间复杂度: O(N * W)。

其中N是重量元素的数量,W是容量。对于每个重量元素,我们遍历所有重量容量1 <= w <= W。

  • 辅助空间: O(N * W)。

使用大小为“N * W”的二维数组。

方法3:使用记忆技术。

方法:此方法基本上是递归方法的扩展,因此我们可以克服计算冗余案例的问题,从而增加了复杂性。我们可以通过简单地创建一个二维数组来解决这个问题,如果我们第一次得到它,它可以存储一个特定的状态(n,w)。现在,如果我们再次遇到相同的状态(n,w),而不是以指数复杂度进行计算,我们可以直接以固定时间返回存储在表中的结果。在此方面,此方法相对于递归方法具有优势。

下面是上述方法的python代码实现

val = [60, 100, 120 ]wt = [10, 20, 30 ]W = 50n = len(val)# We initialize the matrix with -1 at first.t = [[-1 for i in range(W + 1)] for j in range(n + 1)]    def knapsack(wt, val, W, n):    # base conditions      if n == 0 or W == 0:          return 0      if t[n][W] != -1:          return t[n][W]     # choice diagram code      if wt[n-1] <= W:          t[n][W] = max(              val[n-1] + knapsack(                  wt, val, W-wt[n-1], n-1),              knapsack(wt, val, W, n-1))          return t[n][W]      elif wt[n-1] > W:          t[n][W] = knapsack(wt, val, W, n-1)          return t[n][W]print(knapsack(wt, val, W, n))

复杂度分析:

  • 时间复杂度: O(N * W)。

由于避免了状态的冗余计算。

  • 辅助空间: O(N * W)。

使用2D数组数据结构存储中间状态。

推荐阅读

背包问题(01背包问题例题讲解)

趣学算法

陈小玉 著

背包问题(01背包问题例题讲解)

PS:如果遇到有关于百科类创建编辑修改的任何问题,欢迎留言咨询,百科参考网无偿免费回答。请注明出处:https://www.2333.org.cn/2333/1516.html

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注