01背包问题-动态规划算法

转 https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html

一、问题描述：有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

二、总体思路：根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现；

三、动态规划的原理及过程：

　　eg：number＝4，capacity＝8

1、原理

　　动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

2、过程

　　a) 把背包问题抽象化（X₁，X_2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），V_i表示第 i 个物品的价值，W_i表示第 i 个物品的体积（重量）；

　　b) 建立模型，即求max(V₁X₁+V₂X₂+…+VnXn)；

　　c) 约束条件，W₁X₁+W₂X₂+…+WnXn<capacity；

　　d) 定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；

　　e) 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理，采用反证法证明：

　　　　假设(X₁，X₂，…，Xn)是01背包问题的最优解，则有(X₂，X₃，…，Xn)是其子问题的最优解，

　　　　假设(Y₂，Y_3，…，Yn)是上述问题的子问题最优解，则理应有(V₂Y₂+V₃Y₃+…+VnYn)+V₁X₁ > (V₂X₂+V₃X₃+…+VnXn)+V₁X_1；

　　　　而(V₂X₂+V₃X₃+…+VnXn)+V₁X₁=(V₁X₁+V₂X₂+…+VnXn)，则有(V₂Y₂+V₃Y₃+…+VnYn)+V₁X₁ > (V₁X₁+V₂X₂+…+VnXn)；

　　　　该式子说明(X₁，Y₂，Y_3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X₁，X₂，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理；

　　f) 寻找递推关系式，面对当前商品有两种可能性：

　　　　第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；

　　　　第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

　　　　　　　其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；

　　　　由此可以得出递推关系式：

　　　　1) j<w(i)      V(i,j)=V(i-1,j)

　　　　2) j>=w(i)     V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

　　g) 填表，首先初始化边界条件，V(0,j)=V(i,0)=0；

　　h) 然后一行一行的填表，

　　　　1) 如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；

　　　　2) 又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；

　　　　3) 如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10；所以填完表如下图：

 1 void FindMax()//动态规划
 2 {
 3     int i,j;
 4     //填表
 5     for(i=1;i<=number;i++)
 6     {
 7         for(j=1;j<=capacity;j++)
 8         {
 9             if(j<w[i])//包装不进
10             {
11                 V[i][j]=V[i-1][j];
12             }
13             else//能装
14             {
15                 if(V[i-1][j]>V[i-1][j-w[i]]+v[i])//不装价值大
16                 {
17                     V[i][j]=V[i-1][j];
18                 }
19                 else//前i-1个物品的最优解与第i个物品的价值之和更大
20                 {
21                     V[i][j]=V[i-1][j-w[i]]+v[i];
22                 }
23             }
24         }
25     }
26 }

　　i) 表格填完，最优解即是V(number,capacity)=V(4,8)=10，但还不知道解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：

　　　　1) V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；

　　　　2) V(i,j)=V(i-1,j-w(i))+v(i)实时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；

　　　　3) 一直遍历到i＝0结束为止，所有解的组成都会找到。

　　j) 如上例子，

　　　　1) 最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；

　　　　2) 有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；

　　　　3) 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；

　　　　4) 有V(1,0)=V(0,0)=0，所以第1件商品没被选择；

　　k) 到此，01背包问题已经解决，利用动态规划解决此问题的效率即是填写此张表的效率，所以动态规划的时间效率为O(number*capacity)=O(n*c)，由于用到二维数组存储子问题的解，所以动态规划的空间效率为O(n*c)；

 1 void FindWhat(int i,int j)//寻找解的组成方式
 2 {
 3     if(i>=0)
 4     {
 5         if(V[i][j]==V[i-1][j])//相等说明没装
 6         {
 7             item[i]=0;//全局变量，标记未被选中
 8             FindWhat(i-1,j);
 9         }
10         else if( j-w[i]>=0 && V[i][j]==V[i-1][j-w[i]]+v[i] )
11         {
12             item[i]=1;//标记已被选中
13             FindWhat(i-1,j-w[i]);//回到装包之前的位置
14         }
15     }
16 }

3、空间优化

　　l) 空间优化，每一次V(i)(j)改变的值只与V(i-1)(x) {x:1...j}有关，V(i-1)(x)是前一次i循环保存下来的值；

　　因此，可以将V缩减成一维数组，从而达到优化空间的目的，状态转移方程转换为 B(j)= max{B(j), B(j-w(i))+v(i)}；

　　并且，状态转移方程，每一次推导V(i)(j)是通过V(i-1)(j-w(i))来推导的，所以一维数组中j的扫描顺序应该从大到小(capacity到0)，否者前一次循环保存下来的值将会被修改，从而造成错误。

　　m) 同样以上述例子中i=3时来说明，有:

　　　　1) i=3，j=8，w(3)=4，v(3)=5，有j>w(3)，则B(8)=max｛B(8)，B(8-w(3))+v(3)｝=max｛B(8)，B(4)+5｝=max｛7，4+5｝=9；

　　　　2) j- -即j=7，有j>w(3)，则B(7)=max｛B(7)，B(7-w(3))+v(3)｝=max｛B(7)，B(3)+5｝=max｛7，4+5｝=9；

　　　　3) j- -即j=6，有j>w(3)，则B(6)=max｛B(6)，B(6-w(3))+v(3)｝=max｛B(6)，B(2)+5｝=max｛7，3+5｝=8；

　　　　4) j- -即j=5，有j>w(3)，则B(5)=max｛B(5)，B(5-w(3))+v(3)｝=max｛B(5)，B(1)+5｝=max｛7，0+5｝=7；

　　　　5) j- -即j=4，有j＝w(3)，则B(4)=max｛B(4)，B(4-w(3))+v(3)｝=max｛B(4)，B(0)+5｝=max｛4，0+5｝=5；

　　　　6) j- -即j=3，有j<w(3)，继续访问数组会出现越界，所以本轮操作停止，B(0)到B(3)的值保留上轮循环（i=2时）的值不变，进入下一轮循环i++；

　　如果j不逆序而采用正序j=0...capacity，如上图所示，当j=8时应该有B(8)=B(8-w(3))+v(3)=B(4)+5，然而此时的B(4)已经在j=4的时候被修改过了，原来的B(4)=4，现在B(4)=5，所以计算得出B(8)=5+5=10，显然这于正确答案不符合；所以该一维数组后面的值需要前面的值进行运算再改动，如果正序便利，则前面的值将有可能被修改掉从而造成后面数据的错误；相反如果逆序遍历，先修改后面的数据再修改前面的数据，此种情况就不会出错了；

 1 void FindMaxBetter()//优化空间后的动态规划
 2 {
 3     int i,j;
 4     for(i=1;i<=number;i++)
 5     {
 6         for(j=capacity;j>=0;j--)
 7         {
 8             if(B[j]<=B[j-w[i]]+v[i] && j-w[i]>=0 )//二维变一维
 9             {
10                 B[j]=B[j-w[i]]+v[i];
11             }
12         }
13     }
14 }

　　n) 然而不足的是，虽然优化了动态规划的空间，但是该方法不能找到最优解的解组成，因为动态规划寻早解组成一定得在确定了最优解的前提下再往回找解的构成，而优化后的动态规划只用了一维数组，之前的数据已经被覆盖掉，所以没办法寻找，所以两种方法各有其优点。

四、蛮力法检验：

　　1) 蛮力法是解决01背包问题最简单最容易的方法，但是效率很低

　　2) (X₁，X_2，…，Xn)其中Xi＝0或1表示第i件商品选或不选，共有n(n-1)/2种可能；

　　3) 最简单的方式就是把所有拿商品的方式都列出来，最后再做判断此方法是否满足装包条件，并且通过比较和记录找出最优解和解组成（如果满足则记录此时的价值和装的方式，当下一次的装法优于这次，则更新记录，如此下去到最后便会找到最优解，同时解组成也找到）；

　　4) n件商品，共有n(n-1)/2种可能，故蛮力法的效率是指数级别的，可见效率很低;

　　5) 蛮力法效率低不建议采取，但可以用于检验小规模的动态规划解背包问题的正确性和可行性，如下图输出可见，解01背包问题用动态规划是可行的：

五、总结：

　　对于01背包问题，用蛮力法与用动态规划解决得到的最优解和解组成是一致的，所以动态规划解决此类问题是可行的。动态规划效率为线性，蛮力法效率为指数型，结合以上内容和理论知识可以得出，解决此问题用动态规划比用蛮力法适合得多。对于动态规划不足的是空间开销大，数据的存储得用到二维数组；好的是，当前问题的解只与上一层的子问题的解相关，所以，可以把动态规划的空间进行优化，使得空间效率从O(n*c)转化为O(c)，遗憾的是，虽然优化了空间，但优化后只能求出最优解，解组成的探索方式在该方法运行的时候已经被破坏掉；总之动态规划和优化后的动态规划各有优缺点，可以根据实际问题的需求选择不同的方式。

六、引申：

　　动态规划可以解决哪些类型的问题？

　　待解决的原问题较难，但此问题可以被不断拆分成一个个小问题，而小问题的解是非常容易获得的；如果单单只是利用递归的方法来解决原问题，那么采用的是分治法的思想，动态规划具有记忆性，将子问题的解都记录下来，以免在递归的过程中重复计算，从而减少了计算量。