算法实验报告二   动态规划法实验

                       

 

一、实验目的及要求

利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步骤。

要求：设计0/1背包问题的动态规划算法，要求输出背包内物品的最大价值以及选入背包的物品种类。利用c语言（c++语言）实现算法，给出程序的正确运行结果。

二、算法描述

 

通过动态规划来解决背包问题。用一个(n+1)*(C+1)的表来计算V[i,j]的值。只需利用下面的公式依次填这个表V[0…n,0…C]即可。算法如下：

输入：物品集合U＝｛u₁,u₂,…u_n｝,体积分别为s₁,s₂,…s_n, 价值分别为 v₁,v₂,…v_n,容量为C的背包。

输出最大的总价值，且满足当装入物品的总体积小于背包容积C时，输出最大总价值V[n,C]。

 

算法如下：

For i=1 to n

  V[i,0]=0

End for

For j=0 to n

 V[0,j]=0

End for

For i=1 to n

  For j=1 to C

    V[i,j]=V[i-1,j]

    If s_i<=j   then  V[i,j]=max{V[i,j],V[i-1,j-s_i]+v_i}

  End for

End for

Return V[n,C]

  

 

三、调试过程及运行结果

 

在调试过程中出现了好多小问题，一开始结果不对，我通过单步调试一步步的看待填的二维表中的数据。发现大部分V[i][j]对了，但是有极小数的不对。故而我的结果出现了问题。通过将si=bao.capacity[i];  vi=bao.value[i];赋值的地方变了结果就正确了。但是当我进一步想把整个二维表输出时，问题又出来了。我的二维表的最后一列不对，都是0，尽管最后的结果对，但是问题还是不小的。于是我又单步调试，在观看V的过程中发现它的变化范围i是从0变到4,j是从0变到9。而我的源程序中#define n 4，#define C 10。即问题终于找到了，数组分配的空间小了。于是通过将int V[n][C]修正为int V[n+1][C+1];结果完全正确了。在标记选中的商品时让下一行最后一个V[i][C]与上一行最后一个V[i][C]比较，如果下一行的比上一行的大说明此商品被选中了。选中了则将其置1，没选中则将其置0。我采用了书上的例子，商品个数为4，背包总容积为10，第一件商品的体积为2，价值为3；第二件商品的全积为3，价值为4；第三件商品的体积为5，价值为7；第四件商品的体积为7，价值为9。通过for循环输出商品的情况，然后计算出V[n][C]，输出的结果为14，与理论结果一样。然后输出二维表。最后输出选中的商品情况。具体运行结果如下：

运行结果如下：

 

 

 

 

 

 

四、实验总结

输入四件商品，商品的体积分别为2、3、5、7，价值分别为3、4、7、9。首先将商品信息显示一下。如上，然后通过算法计算出了V[n][C]＝14，结果正确。然后为了保证过程的正确性，我把整个二维表输出来了，如上所示，与手算的一样。为了显示出选中了哪些商品，对算法稍作了一些修正。多加了：

  For　i=0 to n

       If  V[i][C]<V[i+1][C]

                select=1

         else

                select=0

这样就可以把那些选中的商品标记出来了。由结果知选中了第一件商品，第二件商品，第三件商品，它们的总价值刚好加起来是14。

总结：通过本次实验加深了我对背包问题算法的理解。而且对动态规范编写代码解决一个实际问题有了进一步的认识。即当算法考虑的原问题的每一个子问题，算法都需要计算一个最优解。换句话说，所有算法生成的表项表示算法考虑的子问题的最优解。这时候用动态规范把每一个最优解求出来（利用递归公式），就能够保证最后求得的一定是最优解。而且动态规划有个特点，即它是由底向上，它实现起来就是利用循环，有时用到一层循环即可，有时要用到两层for循环即可以求解出问题。

 

 

 

五、附录（源程序代码清单）

#include <iostream.h>

#include <stdlib.h>

 

#define n 4

#define C 10

 

int max(int,int);

 

 

struct knapsack

       {

              int capacity[C];

           int value[n];

       }bao;

int max(int a,int b)

{

       if(a>=b) 

              return a;

       else

              return b;

}

 

void main()

{

 

    int V[n+1][C+1];

       int i,j;

       int si;

       int vi;

    int select;

       cout<<"输入物品信息：容量、价值"<<endl;

       for(i=1;i<=n;i++)

       {

              cin>>bao.capacity[i];

              cin>>bao.value[i];

       }

       for(i=1;i<=n;i++)

       {

              cout<<i<<"商品大小："<<bao.capacity[i]<<","<<"价值："<<bao.value[i]<<endl;

             

       }

 

       for(i=0;i<=n;i++)

       {

              V[i][0]=0;

       }

      

       for(j=0;j<=C;j++)

       {

              V[0][j]=0;

       }

 

       for(i=1;i<=n;i++)

       { 

        

             

                 V[i][0]=0;

           si=bao.capacity[i];

                 vi=bao.value[i];

              for(j=1;j<=C;j++)

              {

                

              V[i][j]=V[i-1][j];

             

                     if(si<=j)

                     {

                            V[i][j]=max(V[i][j],V[i-1][j-si]+vi);

                                         

                     }

              }           

             

       }

  cout<<"输出结果V[n,C]="<<V[n][C]<<endl;

  cout<<"------------------------------"<<endl;

  for(i=0;i<=n;i++)

  {

         cout<<"第"<<i<<"次结果"<<endl;

         for(j=0;j<=C;j++)

                cout<<V[i][j]<<' ';

             cout<<endl<<"-------------------------"<<endl;

  }

 

  for(i=0;i<n;i++)

  {

         if(V[i][C]<V[i+1][C])

                select=1;

         else

                select=0;

         cout<<"选中的商品情况:"<<endl<<"select="<<select<<endl;

  }

}

 

师评语：

 

 

 

                               

成绩：√优   良   中   及格   不及格