【算法学习笔记】30.动态规划 01背包和完全背包的关系

首先先说明一下01背包和完全背包问题的区别

01背包：有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci,得到的价值是 Wi。求解将哪些物品装入背包可使价值总和最大。（可以不装满）

完全背包：有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。放入第 i 种物品 的费用是 Ci,价值是 Wi。求解:将哪些物品装入背包,可使这些物品的耗费的费用总和不超过背包容量,且价值总和最大。

先说结论：

两个问题的最优解都要用DP来解决，实现的过程也非常像只是在内层循环中 完全背包是顺序，01是逆序。

原因在于 01背包要保证每次计算前i个物品时，分析第i个物品放还是不放时，要根据的是前i－1个物品的值，因为不能让i进入两次背包。

　　　　而完全背包则必须要在前i个物品的基础上再考虑第i个物品是否加入对当前容量下的w的影响。

01背包问题：

状态转移方程：F［i，v］表示的是前i个物体中选若干个，在容量为V的背包里可以达到的最大价值。

　　　　　　　　F[i,v] = max{F[i − 1,v],F[i − 1,v − Ci] + Wi}

可见计算F[i,v]时，是从i－1阶段的两个状态里转移过来的，一个是如果不放第i个物体时，则前i－1个物体在背包为V的最大价值，一个是如果放第i个物体时，在背包为V－c［i］的最大价值加上Wi。两个里面较大的那个就是结果。

这里是用二维数组表示的，非常容易理解，但是空间复杂度过大，另外也不容易统一，如果用一维数组来进行表示，则在每一个阶段时F［v］如果是左值则表示时当前阶段的，即F[i,v]，如果是右值的话要分两种情况，如果已经更新（重新赋值）过则表示当前阶段的，如果还没有被覆盖过则表示的是上一阶段的，即F[i-1,v]。

如果用一维数组来表示的话，F［v］在左值时表示的是这一阶段的，要保证右面的F［v］是上一阶段的，而F［v－ci］也是上一阶段的，所以～逆序计算！！

再仔细观察这个转移方程，因为在计算F[i,v]时，用到的是F［i－1，v－ci］要想在这时用一维数组F[v-ci]取到这个值，必须保证它没有被更新过，即它暂时还没有被计算，而v－ci < v 所以要逆序进行计算！

这个图片可以说明这个问题。 要注意在每一个阶段（每一行）计算时，都是从C［10］开始到C［0］的。

伪代码：

F [0..V ] ←0

for i ← 1 to N

    for v ← V to Ci 

         F[v] ←max{F[v],F[v−Ci]+Wi}

注意内层循环的顺序和边界。因为在第i阶段，如果v小于第i个物品的大小，肯定放不进去i，所以一定不用更新，不必检测。

完全背包问题：

和01背包最大的区别就在于可以每个无限重复。

所以它的状态转移方程可以写成

　　　　　　　　　　　　F[i,v] = max{F[i − 1,v],F[i,v − Ci] + Wi}

表示如果不放第i个物品则沿用上一阶段的F［v］，如果用了它，则要从包含它的这一阶段的v－ci中累加。

如果用一维数组来表示的话，F［v］在左值时表示的是这一阶段的，要保证右面的F［v］是上一阶段的，而F［v－ci］是这一阶段的，所以～顺序计算！！

伪代码： 

F [0..V ] ←0

for i ←1 to N

　　for v  ←Ci to V

　　　　F[v] ←max(F[v],F[v−Ci]+Wi)

另外，如果把两层循环的顺序颠倒，我们还可以得到一个理解：

F [0..V ] ←0

for v  ←Ci to V

　　tmp ＝ 0

　　for i ←1 to N

　　　　tmp ←max(tmp,F[v−Ci]+Wi)

　　F[v]=tmp

在这种情形下，我们可以认为对于每一个v来说，F[v]存的是针对容量v时n个物品的最大价值方案，在计算每个v时，我们循环试着填入每个物体，找到使F［v］最大的那个物体，然后放入进去。

所以此时的状态转移方程应该写成

　　F[v] = max(i:1~N){F[v-Ci]+Wi}  也就是说每个状态是由它的前N个状态转移而来，这N个状态分别就是v－ci  这样也同时可以保证一个物品可以放多次。

－－－－－－－－－－－

但是为了记忆上的方便可以把01背包和完全背包都用i－v的双层循环，完全背包顺序，01背包逆序，即可。