【算法学习笔记】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背包逆序,即可。

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。