关于01的背包问题，你应该知道！这周我们正式开始讲解背包问题！不过说实话，背包九讲对小白来说确实不友好，看起来还是有点吃力，而且都是假代码，也很难看懂。面试的话，其实掌握01背包和completebackpack就够了，顶多加一个multi-pack就可以了。如果你分不清这几种背包的区别，我在这里画了一张图，如下：SegmentationandSubset1至于BackpacksLecture9中的其他背包，面试几乎不会问他们，都是在比赛层面。leetcode上连多个backpack都没有一道题，所以题库也告诉我们01backpack和completebackpack就够了。完整背包也是01背包的一个小改动，那就是：完整背包的物品数量是无限的。所以，背包问题最重要的理论基础就是01背包问题，一定要理解透彻！leetcode上没有纯01背包问题，都是01背包应用问题，也就是需要转化为01背包问题。所以我先通过纯01背包问题把01背包的原理说清楚。后面讲解leetcode问题的时候，重点是如何转化为01背包问题。之前可能有的记录者已经可以熟练的写背包了，但是只要你认真看完这篇文章，相信你会有意想不到的收获！01背包里有n件物品和一个最大重量为w的背包。第i个物品的权重为weight[i]，得到的值为value[i]。每个物品只能使用一次，找出总价值最大的物品放入背包。动态规划-背包问题这是一个标准的背包问题，所以很多同学看了这个自然会想到背包，甚至不知道暴力解法怎么解。这么一来，我倒是没想到自下而上，而是习惯性的想到了背包，那么暴力解应该怎么办呢？每个item其实只有两种状态，take或者not，所以可以用回溯的方法搜索所有情况下，时间复杂度为，其中n代表item的个数。所以蛮力解决方案是指数时间复杂度。那么优化只需要动态规划的解法！在下面的解释中，我将举个例子：背包的最大重量是4。这些物品是：重量价值物品0115物品1320物品2430背包可以携带的物品的最大值是多少？以下解释和插图中出现的数字均基于此示例。二次元dp阵01背包还是一波五段解析。确定dp数组和下标的含义对于背包问题，有一种写法，就是用二维数组，即dp[i][j]表示取任意一个物品与下标[0-i]，放入容量为j的背包中，最大值是多少。光是看这个二维数组的定义，大家就会有些疑惑。看下图：动态规划-背包问题1.永远记住这个dp数组的意义。下面的步骤都是围绕这个dp数组的意义展开的。如果你一头雾水，我们再回顾一下i代表什么，j代表什么。确定递归公式，复习dp[i][j]的含义：取任意下标为[0-i]的物品，放入容量为j的背包中，最大价值和为多少。那么有两个方向发射dp[i][j]，不放itemi：从dp[i-1][j]发射，即背包容量为j，itemi的最大值不放在里面，此时dp[i][j]就是dp[i-1][j]。（实际上，当物品i的重量大于背包j的重量时，物品i无法放入背包，所以背包中的价值还是和之前一样。)放物品i：由dp[i-1][j-weight[i]]发射，背包容量为j-weight[i]时不放dp[i-1][j-weight[i]]物品i的最大值，则dp[i-1][j-weight[i]]+value[i]（物品i的价值），就是将物品i放入背包得到的最大值，所以递归公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);如何初始化dp数组关于初始化，一定要和dp数组的定义一致，否则公式递归的时候会越来越乱。首先，从dp[i][j]的定义出发，如果背包容量j为0，即dp[i][0]，无论选择哪一个物品，背包价值之和都必须为0。如图：动态规划-背包问题2看其他情况。状态转移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);可以看出，i是由i-1推导出来的，那么当i为0时，就必须进行初始化。dp[0][j]，即：i为0，当存放编号为0的物品时，每个容量的背包可以存放的最大值。那么显然当j
