(华电科院)算法设计与分析实验报告—01背包问题

《(华电科院)算法设计与分析实验报告—01背包问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

课程设计报告(2013--2014年度第一学期)名称：算法设计与分析题目0—1背包问题院系：信息工程班级：网络11k1学号：学生姓名：指导教师：牛华为设计周数：1周成绩：日期：2013年11月15 一、目的和要求了解并掌握动态规划算法；用动态规划算法解决0-1背包问题。二、实验环境用VC6.0软件进行编程三、实验内容0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中的物品的总价值最大?在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分物品i。0-1背包问题是一个特殊的整数规划问题。四、 问题分析在0/1背包问题中物体或者被装入背包或者不被装入背包只有两种选择。 循环变量i、j意义：前i个物品能够装入载重量为j的背包中，数组c意义：c[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值。若w[i]>j第i个物品不装入背包 ，否则若w[i]<=j且第i个物品装入背包后的价值>c[i-1][j]，则记录当前最大价值，替换为第i个物品装入背包后的价值。   其c++部分代码如下：#includevoidknapsack(inta[100][100],ints[100],intv[100],intn,intC){for(inti=0;i<=C;i++){a[0][i]=0;}for(i=1;i<=n;i++){a[i][0]=0;for(intj=1;j<=C;j++){if(s[i]<=j){if(v[i]+a[i-1][j-s[i]]>a[i-1][j])a[i][j]=v[i]+a[i-1][j-s[i]];elsea[i][j]=a[i-1][j];}elsea[i][j]=a[i-1][j];}}} voidoutputsack(inta[100][100],intx[100],ints[100],intn,intC){for(intk=n;k>=1;k--){if(a[k][C]=a[k-1][C])x[k]=0;else{x[k]=1;C=C-s[k];}}x[1]=a[1][C]?1:0;}intmain(){inta[100][100];ints[100];intv[100];intx[100];intC,n;cout<<"请输入物品的总个数n:"<>n;cout<<"请输入背包的总容量C:"<>C;cout<<"请依次输入物品的体积s[i]:"<>s[i];}cout<<"请对应输入物品的价值v[i]:"<>v[i];}knapsack(a,s,v,n,C);outputsack(a,x,s,C,n);//max(s,v);//for(i=1;i<=n;i++)//cout< using namespace std; struct goodinfo {  float p; //物品效益     float w; //物品重量     float X; //物品该放的数量     int flag; //物品编号 };//物品信息结构体  void Insertionsort(goodinfo goods[],int n)//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序 {  int j,i;     for(j=2;j<=n;j++)     {        goods[0]=goods[j];         i=j-1;                       while (goods[0].p>goods[i].p)         {    goods[i+1]=goods[i];             i--;         }   goods[i+1]=goods[0];      } }//按物品效益，重量比值做升序排列void bag(goodinfo goods[],float M,int n) {   float cu;     int i,j;     for(i=1;i<=n;i++)     goods[i].X=0;     cu=M;  //背包剩余容量 for(i=1;i>n;         goods=new struct goodinfo [n+1];//         cout<<"请输入背包的最大容量：";         cin>>M;        cout<>goods[i].w;             cout<<"请输入第"<>goods[i].p;   goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比             cout< to run agian"< to exit"<>j;}}七、运行结果： 上述结果显示:贪心算法不是总是最优的.八、动态规划与贪心算法比较动态规划法又和贪婪算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。