这篇文章为你提供什么？

我会从零开始推导0-1背包问题，包括0-1背包的子问题划分、最优子结构的证明、状态转移方程、优化空间复杂度以及0-1背包模板。总之0-1背包的一切都在这了。

0-1背包问题描述

给定n种物品和一个背包。物品i的重量是 Wi，其价值为 Vi，背包的容量为 C，问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品 i 只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品，因此称之为0-1背包问题。

简单的表示就是出来就是这样一个最优化问题

讯享网
其中的xi代表第i个物品取1或0个，也就是要么拿第i个物品，要么不拿第i个物品。对于拿走的物品有个约束就是总重量不可以超过背包的容量C。而最终的结果就是求一个01序列[X1, X2, X3 … Xn]和能拿到的最大价值。

子问题划分

对于这样的大问题我们几乎无法下手，所以可以考虑将大问题划分为小问题（子问题）。减一策略是经常使用的划分策略（一大类动态规划问题都是这个思路）。顾名思义，“减一”就是从大问题中减去一个，形成子问题。在背包问题中，大问题是[X1, X2, … Xn-1, Xn]，减去一个就是[X1, X2, … Xn-1]，对应的描述就是
这个式子与原问题只有两处不同，一处是累加求和到n-1（减一），另一处是背包容量上限为C-WnXn（若Xn=0，背包容量还是C；若Xn=1，容量就得用掉一部分；两种情况合起来就是C-WnXn；这就相当于子问题有两种情况：拿或者不拿第n个物品）。

但是我们必须证明，原问题和子问题拥有相同的[X1, X2, … Xn-1]，否则上面的划分方式就没有意义了。

最优子结构

先说什么是最优子结构，一句话：原问题的最优解，包含了子问题的最优解。
举个例子：今年过年我想从天津想去上海，我希望找一条最短的路线。假设最短的路线是[天津，泰安，徐州，南京，上海]（原问题最优解），如果从天津到南京最短的路线一定也是[天津，泰安，徐州，南京]（子问题最优解），而不是什么其他的方法，我们就说这是具有最优的子结构。问题的规模减了1，问题的解也减了1（包含）。

最优子结构证明

现在证明0-1背包的符合最优子结构的特征。
目标：当原问题取得最大价值时的解序列[X1,X2, … Xn-1,Xn]减一，得到的[X1,X2,…Xn-1]也是子问题的最优解。
证明（反证法）：
如果[X1,X2, … Xn-1]不是子问题的最优解，那么子问题至少存在一个更好的解[X’1,X’2, … X’n-1]，满足
由此构造原问题的新解 不等式说明，原问题的新解是一个更大的解，这与假设矛盾！
因此，当原问题取得最大价值时的解序列[X1,X2, … Xn-1,Xn]减一，得到的[X1,X2,…Xn-1]也是子问题的最优解 。也就是最优解[x1,x2, … Xn-1,Xn]一定是从子问题最优解[X1,X2, … Xn-1]加一构造而成的！这就证明了用减一策略划分，是符合最优子结构的。

子问题的表示和状态转移方程

上面原问题分成了两个子问题，原问题和子问题只有考虑的物品数量和背包的容量两个参数不同。因此使用这两个参数就能描述当前的子问题。

定义dp[i][j]代表考虑前i个物品并且背包容量为j时可以取得的最大价值。我们把dp[i][j]叫做“状态”，一个状态说白了就是一个子问题，状态是参数化的子问题，记录了这个子问题的解。从子问题到原问题，就是从一个状态转移到另一个状态的过程。

因此我们可以用递推方程来描述原问题和子问题之间转化的方式（减1） dp[i][j] = max(dp[[i-1][j-0*Wi], dp[[i-1][j-1*Wi]+vi)

由于第i个物品只有两种情况：拿或者不拿，因此考虑第i个物品能够得到的最大收益只有两种可能性：

• 不拿第i个物品，此时dp[i][j] = dp[i-1][j]
• 拿走第i个物品，此时dp[i][j] = dp[i-1][j-Wi]+Vi
dp[i-1][j]是子问题1。dp[i-1][j-Wi]是子问题2（当前容量j - 第i个物品重量）。

取最大值就有dp[i][p]=max(子问题1, 子问题2+第i件物品的价值)，从而得出了状态转移方程。
简化后dp[i][j]=max(dp[[i-1][j], dp[[i-1][j-Wi]+Vi)

问题求解

举个例子：考虑5个物品，背包容量C为10，重量和价值如下

按照转移方程可以画出自顶向下的划分流程
结点是×表示当前的子问题剩余的容量装不下第i个物品了。

颜色相同的框框代表相同的子问题，显然没必要计算两次同样的问题！我们只要记录下这个答案，等下次遇到相同问题时直接拿出来就成！这也是动态规划的聪明地方。

从图中可以清楚的看出整个问题的递归过程，这里其实就可以使用递归的方式求解了。不过递归会产生额外的开销，如果自底向上的考虑就可以消除递归。

自底向上计算

细心的我们发现，递归到叶子结点可以直接得到答案。如果只考虑一个物品1，能放进容量为j的背包，最大价值就是V1；放不进去就是0。
下面表格中蓝色部分是所有可能的叶子结点。
下面的每一行都可以用dp[i][j]=max(dp[[i-1][j], dp[[i-1][j-Wi]+Vi)计算，注意第i行从Wi开始计算就行，背包容量小于Wi没可能装得下第i个物品。
继续填完剩下的表格填完表格后，dp[5][10]就是问题的最优解了！

代码框架

int dp[1~n][0~C]; for i = 1 to n for j = Wi to C dp[i][j]=max(dp[[i-1][j], dp[[i-1][j-Wi]+Vi) 

算法的时间复杂度O(nC)，空间复杂度O(nC)

优化空间复杂度

仔细观察上面的表格和递归树，当计算第i行（层）的时候只需要i-1行（层）的数据，其他的都可以丢掉。因此可以只开C+1容量的一维数组存储子问题。
但必须从右向左填写这个一维数组，原因是dp[i][j]的子问题只出现在i-1行的第j列的左边，对应到一维数组就是dp[j]和dp[j-Wi]，我们必须保留子问题的答案直到不再有原问题需要它时。

讯享网int dp[0~C]; for i = 1 to n for j = C to Wi dp[j]=max(dp[j], dp[j-Wi]+Vi) 

更多的背包问题

0-1背包是最基础的一种背包问题，稍微更改以下条件就能得到新的背包问题。比如每个物品可以拿无限多个；每个物品最多能拿限定多个；物品能否正好凑成某个价值；满足某个价值有几种取物品的方法，这些是在0-1背包的基础之上衍生出来的。
如果希望了解更多，可以关注我的微信公众号：计万鹏是个程序员，后续我会更新更多的背包问题解题思路。