重新看了一下01背包的问题，感觉自己对于它的理解更加深了，而且还看到了几个便于理解的例子，和大家分享一下。
万变不离其宗，要解决问题，先需要看到问题的本质，对于01背包，它要解决这样一类问题：
有N件物品和一个容量为V 的背包。放入第i件物品耗费的空间是C[i]，得到的价值是W[i]。求解将哪些物品装入背包可使价值总和最大。
我们定义规则，F(i,v)表示将前i件物品放入容量为v的背包中能得到的最大价值，那么递推公式就是
F(i,v)=max(F(i-1,v),F(i-1,v-1))
这个递推公式可以这样理解，如果要求出前i件物品放在容量为v的背包中所获得的最大价值，向前推一个状态，即考虑第i件物品是否放入背包，如果第i件物品不放入背包，那么就将前i-1件物品放入容量为v的背包，获得的价值就是F(i-1,v)，如果第i件物品放入背包，那所剩的空间为v-C[i]，所以就将前i-1件物品放入容量为v-C[i]的背包，这时候获得的价值就是F(i-1,v-C[i])，通过比较这两个价值的大小，我们就可以知道到底第i件物品要不要放了，网上很多例子都用伪代码，我总是觉得看着不顺眼，所以就用C++的代码表示
for(i=1;i<=N;i++)
{
<span style="white-space:pre"> </span>for(j=v[i];j<=V;j++)
{
F[i][j]=max(F[i-1][j],F[i-1][j-v[i]]+W[i]);
}
}
这里需要对F做一个初始化，因为将0件物品放入背包和将物品放入容量为0的背包所得到的价值都是0，于是F[0][ ]和F[ ][0]都应该初始化成0，然后，最后算出来的那个数就是我们要求的最大价值。
这个递推公式虽然好理解，但很明显空间复杂度较高，因为是一个二维数组，所以我们一般不用这种方式，而是只使用一维数组来存储，下面讲一下是如何实现的。
从上面的递推公式我们可以看到，当求F(i,v)的时候，它是由F(i-1,v)和F(i-1,v-C[i])决定的，可以看出，假如我们将i理解为时刻的话，那么第i个时刻的状态只与第i-1个时刻有关，那么我们现在定义一个一维数组F[v]，用来表示背包的容量为v时所能得到的最大价值，那么递推公式可以这样表示，F[v]=max(F[v],F[v-C[i]]+W[i])，注意，假如等式左边的F[i]是我们要求的第i个时刻的最大价值的话，那么等式右边的F[i]则表示的是i-1时刻的最大值，这样才能表示出第i件物品不放的情形，也就是说，在我们求第i个状态之前，第i-1个状态是绝对不能改变的，所以，我们必须从后往前遍历数组F，数组的每一个元素代表一个状态，并且从左往右状态依次增加。下面是代码
for(i=1;i<=N;i++)
{
for(j=V;j>=C[i];j--)
{
F[j]=max(F[j],F[j-C[i]]+W[i]);
}
}
下面在给大家说一下关于细节处理的问题，这里参考了背包九讲
因为这种问题经常有两种问法：1背包恰好装满，2单纯的寻求最大价值
对于第一种情况，我们可以将F数组除第一个元素外全都初始化为-∞，第一个元素则初始化为0，可以这样理解，如果要恰好装满背包，那么一开始的时候因为还没有装进物品，所以只有容量为0的背包才是一个合法的状态，因为相当于它已经恰好装满了。
对于第二种情况，因为不要求恰好装满，所以每一个状态都应该是合法的，于是就全部初始化为0就可以了。