01背包问题新手详解

首先，这是一个纯新手向的01背包问题详解，且不包含优化部分，因为优化本人还在研究学习，好了，言归正传，接下来开始进行个人理解的讲解。

01背包问题是动态规划里面一个比较难的问题了，因为他的状态方程转移比较难读，很多同学可能和我一样，感觉有点理解，似乎懂了，但是又没有真正的理解，总是照不出来症结所在，其实，难点就是2维的状态转移方程的逻辑以及判断过程。接下来我们会详细的文字分析这个过程。

对于状态转移方程，我们举一个最标准的例子，就是空间价值问题，装入物品，然后价值不同，且每个物品只有一个，我们这里采用经典解法，也就是实现二维数组的背包问题，我们设定一个dp[n+1][m+1]，表示一个背包，大小为m，然后我们准备了n个物品，dp[i][j]，即表示当前背包下，i个物品准备装入大小为 j 的背包的时候的最优解。现在不需要疑问为什么这么设计，后面我们读到实现部分就会豁然开朗的。

首先，我们很容易可以知道，假如 i=0，或者 j=0的时候，也就是没有物品或者背包大小为 0 的时候，结果一定是0。也就是 dp[0][ ] dp[ ][0]一定是0。这个是显然成立的，然后，我们分析从上到下，从左到右的分析这个数组的变化，这里用例子会很好理解，例如，我们有三个物品， 1 ：2，3；表示2大小，价值为3，第二个物品，2：3，5；第三个物品3：4，6；

这时候我们有一个初始的表格如图所示

然后我们手动的去模拟这个背包问题的函数执行。当 i = 1的时候，我们认为这时候只有一个物品，那么这时候，我们比较这个物品的大小，对于 j = 1 的时候，背包大小为1，这时候我们进行判断，是否可以装入，否，这时候的最优解就是上次的同大小背包的最优解，直接抄写下来，然后大小为2，这时候判断是否可以装入，是，然后我们进行两个操作，装入，或者不装入，假如不装入，就和上个一样，直接抄写，假如装入，这时候，背包问题转化，当前的背包问题变成背包大小 -2，物品减去本物品，变成如图所示的状态：

这个变化就是背包问题的递归核心，如果这时候还没完全清晰，我会逐渐的讲解，直到整个表格生成，这个过程还会多次出现，同学们自然会彻底理解的。

然后，我们根据上面的操作，可以知道，现在装入的结果就是3+0，比较直接抄写上面的结果 0，显然，现在的最优解就是3。之后我们按照这样的操作写完第一行。

然后我们接着写第二行，也是一样的，先比较当然物品的大小，看是否能装入，这时我们只考虑当前物品是否能装入，这时候，1，2大小都无法装入，这时候，我们抄写上面的结果，就是问题缩减为无法装入该物品，减去该物品，自然就是前面物品的最优解，这个抄写，想必大家都很清楚了，就变成了这样的结果：

然后当背包大小为3的时候，判断，可以装入，两种操作，装入，背包缩小为3-3，可装入物品减去本物品，就缩减为如图：

这时候，结果就是 5+0，假如不装入，就是上一次的最优解，比较发现，对于本次，肯定是采用装入的手段最好，然后这个位置就变成了5，之后的内容，我们按照这个规则继续填入，就得到了如图：

这里需要对背包大小为5的情况进行一次分析，因为可以加深理解。背包大小5的时候，判断当前物品是否可以装入，可以，假如装入，问题缩减为如图：

这时候，最优解就右下角，结果就是 5+3，假如不装入，就是直接抄下来上面的，其实也是一种问题缩减，即变成了：

这时候，最后的结果最优自然就是8，然后我们按照同样的道理就可以把整个表完成，就得到了：

到这一步，想必大家都已经彻底理解了背包问题的核心，状态方程转换原理了。

其实，对于完全背包问题，逻辑上一样的，只是，这时候我们的问题缩减中不会缩减物品，只会缩减背包。

本文基于bilibili的阿帕奇biubiubiu大佬制作的：01背包动画讲解，制作。里面加上了一些个人的理解，希望同同学们一起进步~