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

无论是脸书、谷歌、微软、百度、阿里、腾讯...每年大厂在面试时总会考查动态规划问题。作为动态规划问题中非常重要的一类——背包问题，慢慢走到了舞台中央，成为高频面试题中的“佼佼者”。

背包问题举例:在保持重量小于等于15 kg的情况下，选择哪些箱子使价格尽可能大？图片来自:维基百科-背包问题

随着面试算法岗位的人越来越多，背包问题也不像以前那么“无辜”，现在充满了“套路”。0-1背包、多个背包、完整背包等背包问题，在经历了大厂面试官不断变化的提问、表情、套路后，让无数面试官短时间内找不到问题需求，内心os“这个问题你想干什么？”。很多人都在背包问题上跪着。......

图片来自:谷歌图片滑稽表情包

背包问题看似简单的数学问题，背后的算法逻辑却相当复杂，短时间内分析不出来基本就是凉的。很多人可能只是因为面试的时候没有做出背包的问题就被大厂拒绝了。怎样才能快速掌握背包问题求解套路，成为大厂报价收割机？

和任友君一起快速掌握背包问题解决技巧，go！

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

什么背包问题？

背包问题是一个组合优化的NP完全问题。

问题可以描述为:给定一组物品，每个物品都有自己的重量和价格。在有限的总重量内，如何选择才能让物品总价最高？

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

背包问题有哪些？

背包问题分为以下五类:

0-1背包问题

多重背包问题

完全背包问题

分组问题

混合背包问题

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

背包问题是互联网公司最常见的算法面试问题，因其代码量小、思考量大而深受面试官喜爱。另外，背包问题是学习动态规划的基础，是动态规划初级阶段必须掌握的问题。这也是为什么背包问题正在成为大厂高频面试题中的“极品”。掌握0-1背包、多背包、完全背包等背包问题的解法，可以加深初学者对动态规划中状态的理解。

0-1背包问题

问题描述

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

W=50 .

解决问题的方法

方法:采用暴力算法或穷举法进行递归。

方法:一个简单的解决方案是考虑项目的所有子集，并计算所有子集的总权重和值。只考虑总权重小于w的子集。从所有这些子集中，选择最大子集。

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

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

2:该商品不包含在最佳组合中。

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

n-1项和w权(不包括第n项)得到的最大值。

第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()。

因为有多余的子问题。

辅助空房间:O(1)。

因为没有额外的数据结构来存储值。

2.通过自下而上构造临时数组K[][]，可以避免重新计算同一个子问题。

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

现在可能发生两种情况:

在给定栏中填写作业指导书。

不要在给定栏中填写作业指导书。

现在，我们不得不最大限度地考虑这两种可能性。形式上，如果我们在第j列不填充ith weight，DP[i][j]的状态将与DP[i-1][j]的状态相同，但如果我们填充weight，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] 

以上就是由优质生活领域创作者 嘉文社百科网小编 整理编辑的，如果觉得有帮助欢迎收藏转发~