动态规划解决0-1背包问题

这个是网上比较好的案例，因为原文有些地方晦涩难懂，对于刚接触动态规划问题的朋友来说很不友好，所以很对地方加入了我自己的见解，也是作为我的一次学习历程。

一、问题描述：

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

二、总体思路：

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

三、动态规划的原理及过程：
一个案例：有4个物品，其体积w={2,3,4,5}，其价值依次为v={3,4,5,6}，背包的容量为8。如何将物品装入背包使得其总价值最大？
　

1、原理

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

动态规划步骤

1）找出最优解的性质，并刻画其结构特征
2）递归的定义最优值
3）以自第向上的方式计算出最优值
4）根据计算最优值时得到的信息，构造一个最优解

2、过程

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

b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；

c) 约束条件，W1X1+W2X2+…+WnXn<capacity；

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

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

假设(X1，X2，…，Xn)是0-1背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解，

假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1；

而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)，则有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V1X1+V2X2+…+VnXn)；

该式子说明(X1，Y2，Y3，…，Yn)才是该0-1背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故0-1背包问题满足最优性原理；

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)表示不装第i号物品的价值，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；

由此可以得出递推关系式：（i是物品编号，j是背包剩余容量）

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) ｝注意：大写V(i-1,j-w(i))表示可装入背包中的在背包容量为j-w(i)前提下，前（i-1）个商品的最大总价值，小写v(i)表示第i个商品的价值。

g) 填表，首先初始化边界条件，V(0,j)=V(i,0)=0；（解析：结合下图分析，V(0，j)表示物品是 0，即背包中不放入任何物品，所以背包的价值为0;V(i，0)表示背包的容量为0，所以背包中放不下任何物品，所以其价值也为0，所以第一行和第一列均为0！）
　　　h) 然后一行一行的填表

1) 如：i=1，j=1，w(1)=2，v(1)=3，（即当背包容量为1的情况下，1号物品能能否放入背包）因为j=1，w(1)=2，j < w(1),故物品1不能放进背包，所以V(1,1)=V(1-1,1)=0；

2) 又如i=1，j=2，w(1)=2，v(1)=3，（即在容量为2的情况下，1号物品能否放入背包）因为j=2, w(1)=2,j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3（放入1号物品的价值是3，不放入1号物品的价值是0，选择价值大的操作）；

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（如果装入物品4,则在剩余背包容量中（8-5=3）中选取1、2、3号物品装入可获得最大价值的组合+当前物品的价值与不放入该物品的最大价值相比较，取最大的即可）。所以填完表如下图：

void FindMax()//动态规划
{
   int i,j;
   //填表
   for(i=1;i<=number;i++)
   {
       for(j=1;j<=capacity;j++)
       {
           if(j<w[i])//包装不进
           {
               V[i][j]=V[i-1][j];
           }
           else//能装
           {
               if(V[i-1][j]>V[i-1][j-w[i]]+v[i])    //不装价值大
               {
                   V[i][j]=V[i-1][j];
               }
               else//前i-1个物品的最优解与第i个物品的价值之和更大
               {
                   V[i][j]=V[i-1][j-w[i]]+v[i];
               }
           }
       }
   }
}

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

1) V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，即在背包容量为j的情况下，前i个商品的最优值与前（i-1）个商品的最优值相同，则回到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) 根据我们举的案例，我们从价值最大的10开始自底向上查找都是哪些物品装入了背包：

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) 到此，0-1背包问题已经解决，利用动态规划解决此问题的效率即是填写此张表的效率，所以动态规划的时间效率为O(numbercapacity)=O(nc)，由于用到二维数组存储子问题的解，所以动态规划的空间效率为O(n*c)；

查找解的最优组成

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