在学习代码编程的过程中，我们会看见一个经常出现的一个词：动态规划。

动态规划是我们学习算法的重要一环，它的核心在于问题的状态转移。只要我们可以通过我们的数学分析出问题的状态转移方程，问题就可以迎刃而解。

而我们学习动态规划的第一步，就要学习01背包问题。

鄙人也刚学了背包问题，发篇文章分享自己的学习理解，若有不足希望各位指出，也欢迎各位提问。

初讲代码：

问题是这样的：

现有n个物品，各个物品有各个物品所占体积和其价值，我们有一个最大体积为V的背包，那么请通过编程写一个让我们可以在最大体积为V的情况下拿到最大的物品价值。

数据给出： 背包体积为8

例题数据

根据上文所述，我们第一步就要用计算思维想出它的状态转移方程。

对于最优解的求法：我们可以一遍扫过所有数据，然后对每一个数据进行选择：拿上去和不拿。

我们用数组V存放第i个物品的价值，用数组W存放第i个物品的重量，用dp二维数组进行我们的计算数据存储。

这个解法也通俗易解，因为我们平时都是这样在思考这类问题的。

核心思路

所以我们就用这种方法写出代码：

代码实现

其中有一个问题是： 既然我们规定j是剩余的背包体积，为什么j是从1到v呢？

我们换个角度考虑，如果手上有100元钱，我们如何最大化它的价值可能有点模模糊糊，但是我们手上只有4元的时候我们就可以合理的规划。

这样我们的每一部分的体积都是被合理规划好的。

所以初步代码我们已经写成，详细计算机计算的过程大家可以遍历数组观察分析。

优化

但是这个代码的有个不足之处，它虽然容易理解，但是它的二维数据导致它的时间，空间复杂度都很高，我们代码就要精益求精，所以就有了个更高级的版本。

我们观察，对于上面的dp遍历过程，前几层的dp结果并不影响最终的结果，所以我们可以选择更加优秀的方法：对已经过时的数据进行覆盖。

所以我们就可以有另一种写法

talk is cheap ，show me your code！

优化代码

而这里的j为什么是从最大值到w【i】呢，我也是查阅了很多的资料才搞明白的。

我们上一部分代码，用逆序的方法从1到最大体积V，这样的方法使得每一部分的体积都是好好被利用的。

而我们上一部分的代码的第i层是用来更新每一组的计算数据的。

但是我们这次的一位数组并没有第i层来更新数组，dp[V]相当于求二维数组下的dp[i][V],因为顺序是从右向左，所以当前dp[V](还没更新，这步正准备更新dp[V])表达的是二维数组下的dp[i-1][V](表达的是之前存放i-1个物品时的最大值),dp[V-w[i]]相当于dp[i-1][V]。所以和二维数组存储效果相同。如果从左到右遍历的话会出问题。比如我先把dp[V-w[i]]更新了，表示我已经算好了在V-w[i]容量下判断存放第i个物品的最大价值，然后往右遍历到dp[V],现在想求在V容量下判断存放第i个物品的价值，但是之前更新过的dp[V-w[i]]已经更新到i了，与dp[V]需要dp[V-w[i]]处于i-1状态的要求不符（可以类比一下二维原式:dp[i][j] = max(dp[i-1][j - w[i]] + v[i], dp[i-1][j]注意到max函数里面数组下标都是i-1)。（一个前辈的解释）。