01背包算法的理解

01背包问题：

有N件物品和一个最大重量限制为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过V，且价值总和最大。每个物品只有1份，且不可分割

 

看了01背包算法，言简意赅，但理解起来头昏脑胀，不得要领。尝试解释下对该算法的理解，加深记忆。

假设最优解已经存在，怎么判断一个物品i是否在背包里？  简单，只要知道，

1、c[i]是否大于V，

2、F[i-1][V-c[i]]，即没有i物品的情况下，最大重量限制为V-c[i]的最优解。

3、F[i-1][V]，即没有i物品的情况下，最大重量限制为V的最优解。

如果F[i-1][V-c[i]]+w[i]>F[i-1][V],那最优解就包含i。问题转到了求没有i物品的N-1件物品，最大重量为V和V-c[i]的两个背包的最优解。递归下去最终会求只有1件物品、0件物品的最优解。只有k（k=0、1、2。。N）件物品的时候，需要求最大重量为多少的背包的最优解？不知道，但可以从最大重量0到V的背包都求最优解。

这样，要求N件物品，最大重量限制为V的背包的最优解，那就先求有0个物品，0--V个背包的最优解（0个物品时任何背包的最优解都是0，最大重量限制为0的背包，不管多少个物品的最优解也是0），然后顺序计算只有前1、2…..N个物品的最优解，F[k][V]=max{ F[k-1][V-c[k]]+w[k] ,F[k-1][v]}。这样，就得到F[N][V]的最优解了。