背包问题（01背包问题例题讲解）

　　背包问题（01背包问题例题讲解）2021040718：30人民邮电出版社无论是Facebook、Google、Microsoft，还是百度、阿里、腾讯每年大厂面试时总会考察动态规划问题。而作为动态规划类问题中非常重要的一个类别背包问题，慢慢地走到了舞台中央成为面试高频题中的佼佼者。
　　背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15kg？图片源自：维基百科背包问题
　　随着面试算法岗位的人数不断增多，背包问题也不像当初那样天真无邪，如今也是套路满满。01背包，多重背包，完全背包等背包问题，经历大厂面试官变题型、换表达、改套路之后，让无数面试者短时间内无法找到问题需求，内心os这题想干嘛？。很多人都在背包问题上，跪了。。。。。。
　　图片源自：谷歌图片搞笑表情包
　　背包问题看起来是个简单的数学问题，但背后的算法逻辑相当复杂，短时间分析不出来，基本上就凉凉了。很多人在面试过程中可能就是因为没有做出一道背包问题，而被大厂拒之门外。如何才能快速掌握背包问题的解题套路，成为大厂offer收割机呢？
　　跟人邮君一起快速掌握背包问题解题技巧，go！趣学算法（异步图书出品）77。4购买什么背包问题？
　　背包问题（Knapsackproblem）是一种组合优化的NP完全问题。
　　问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
　　相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V。背包问题有哪些？
　　背包问题分为以下五种：
　　01背包问题
　　多重背包问题
　　完全背包问题
　　分组背包问题
　　混合背包问题学习背包问题有什么作用？
　　背包问题是互联网公司最常见的算法面试题，由于其代码量较小而思维量较大的特点而深受面试官的钟爱。此外，背包问题是学习动态规划的基础，是动态规划入门阶段必须要熟练掌握的问题。这也是为什么背包问题日渐成为大厂面试高频题中的佼佼者的原因所在。熟练掌握01背包，多重背包，完全背包等背包问题的解法，可以加深初学者对于动态规划中状态的理解。01背包问题
　　问题描述
　　给定n个物品的权重和值，将这些物品放在容量为W的背包中，以在背包中获得最大的总价值。换句话说，给定两个整数数组value〔0。。n1〕和weight〔0。。n1〕，它们分别表示与n个项目相关联的值和权重。还给定代表背包容量的整数W，找出val〔〕的最大值子集，以使该子集的权重之和小于或等于W。本题中value〔〕｛60，100，120｝，weight〔〕｛10，20，30｝，
　　W50。
　　解题方法方法1：通过蛮力算法或穷举搜索进行递归。
　　方法：一种简单的解决方案是考虑所有项目子集，并计算所有子集的总重量和价值。仅考虑总权重小于W的子集。从所有此类子集中，选择最大值子集。
　　最佳子结构：要考虑项目的所有子集，每个项目可能有两种情况。
　　情况1：该项目包含在最佳子集中。
　　情况2：该商品未包含在最佳组合中。
　　因此，可以从n个项目中获得的最大值是以下两个值中的最大值。
　　通过n1个项和W权重（不包括第n个项）获得的最大值。
　　第n个项目的值加上n1个项目获得的最大值，W减去第n个项目（包括第n个项目）的权重。
　　如果第n个项目的权重大于W，则第n个项目不能包括在内，情况1是唯一的可能性。
　　下面是上述方法的python代码实现defknapSack（W，wt，val，n）：BaseCaseifn0orW0：return0IfweightofthenthitemismorethanKnapsackofcapacityW，thenthisitemcannotbeincludedintheoptimalsolutionif（wt〔n1〕gt；W）：returnknapSack（W，wt，val，n1）returnthemaximumoftwocases：（1）nthitemincluded（2）notincludedelse：returnmax（val〔n1〕knapSack（Wwt〔n1〕，wt，val，n1），knapSack（W，wt，val，n1））endoffunctionknapSackDriverCodeval〔60，100，120〕wt〔10，20，30〕W50nlen（val）printknapSack（W，wt，val，n）
　　复杂度分析
　　时间复杂度：O（）。
　　由于存在多余的子问题。
　　辅助空间：O（1）。
　　由于没有额外的数据结构用于存储值。方法2：通过自下而上的方式构造临时数组K〔〕〔〕，可以避免重新计算相同子问题。
　　方法：在动态编程中，我们将考虑与递归方法中提到的情况相同的情况。在DP〔〕〔〕表中，让我们将从1到W的所有可能的权重视为列，并将权重保留为行。考虑到从1到第i的所有值，状态DP〔i〕〔j〕将表示jweight的最大值。因此，如果我们考虑wi（ith行中的权重），则可以将其填充到weightvaluegt；wi的所有列中。
　　现在可以发生两种可能性：
　　在给定的列中填写wi。
　　不要在给定的列中填写wi。
　　现在，我们必须最大限度地考虑这两种可能性，形式上，如果我们不在jth列中填充ith权重，则DP〔i〕〔j〕状态将与DP〔i1〕〔j〕相同，但是如果我们填充权重，则DP〔i〕〔j〕将等于wi的值上一行中权重为jwi的列的值。因此，我们将这两种可能性中的最大值用于填充当前状态。
　　下面是上述方法的python代码实现：defknapSack（W，wt，val，n）：K〔〔0forxinrange（W1）〕forxinrange（n1）〕BuildtableK〔〕〔〕inbottomupmannerforiinrange（n1）：forwinrange（W1）：ifi0orw0：K〔i〕〔w〕0elifwt〔i1〕lt；w：K〔i〕〔w〕max（val〔i1〕K〔i1〕〔wwt〔i1〕〕，K〔i1〕〔w〕）else：K〔i〕〔w〕K〔i1〕〔w〕returnK〔n〕〔W〕Drivercodeval〔60，100，120〕wt〔10，20，30〕W50nlen（val）print（knapSack（W，wt，val，n））
　　复杂度分析
　　时间复杂度：O（NW）。
　　其中N是重量元素的数量，W是容量。对于每个重量元素，我们遍历所有重量容量1lt；wlt；W。
　　辅助空间：O（NW）。
　　使用大小为NW的二维数组。方法3：使用记忆技术。
　　方法：此方法基本上是递归方法的扩展，因此我们可以克服计算冗余案例的问题，从而增加了复杂性。我们可以通过简单地创建一个二维数组来解决这个问题，如果我们第一次得到它，它可以存储一个特定的状态（n，w）。现在，如果我们再次遇到相同的状态（n，w），而不是以指数复杂度进行计算，我们可以直接以固定时间返回存储在表中的结果。在此方面，此方法相对于递归方法具有优势。
　　下面是上述方法的python代码实现val〔60，100，120〕wt〔10，20，30〕W50nlen（val）Weinitializethematrixwith1atfirst。t〔〔1foriinrange（W1）〕forjinrange（n1）〕defknapsack（wt，val，W，n）：baseconditionsifn0orW0：return0ift〔n〕〔W〕！1：returnt〔n〕〔W〕choicediagramcodeifwt〔n1〕lt；W：t〔n〕〔W〕max（val〔n1〕knapsack（wt，val，Wwt〔n1〕，n1），knapsack（wt，val，W，n1））returnt〔n〕〔W〕elifwt〔n1〕gt；W：t〔n〕〔W〕knapsack（wt，val，W，n1）returnt〔n〕〔W〕print（knapsack（wt，val，W，n））
　　复杂度分析：
　　时间复杂度：O（NW）。
　　由于避免了状态的冗余计算。
　　辅助空间：O（NW）。
　　使用2D数组数据结构存储中间状态。
　　推荐阅读
　　趣学算法
　　陈小玉著