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

课程设计报告 ( 2013 - 2014 年度第 一 学期)名 称： 算法设计与分析 题 目 01背包问题 院 系： 信息工程 班 级： 网络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意义：cij表示前i个物品能装入载重量为j的背包中物品的最大价值。若wij第i个物品不装入背包，否则若wici-1j，则记录当前最大价值，替换为第i个物品装入背包后的价值。其c+部分代码如下：#includevoid knapsack(int a100100,int s100,int v100,int n,int C)for(int i=0;i=C;i+)a0i=0;for( i=1;i=n;i+) ai0=0;for(int j=1;j=C;j+)if(siai-1j)aij=vi+ai-1j-si;elseaij=ai-1j;elseaij=ai-1j;void outputsack(int a100100, int x100,int s100,int n,int C)for(int k=n;k=1;k-)if(akC=ak-1C)xk=0;elsexk=1; C=C-sk;x1=a1C?1:0;int main()int a100100;int s100;int v100;int x100;int C,n;cout请输入物品的总个数n:n;cout请输入背包的总容量C:C;cout请依次输入物品的体积si:endl;for(int i=1;isi;cout请对应输入物品的价值vi:endl;for( i=1;ivi;knapsack(a,s,v,n,C);outputsack(a,x,s,C,n);/max(s,v);/for( i=1;i=n;i+)/coutxi;cout最大价值是：endl;coutanCendl;return 0;五、调试过程及实验结果六、总结01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。实验二：贪心算法解01背包问题一、实验目的学习掌贪心算法法思想。二、实验内容用贪心法求解01背包问题，并输出问题的最优解。问题描述：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。三、实验条件用VC6.0软件进行编程。四、需求分析对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化。五、基本思想：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。总是选择单位价值最高的物品六、代码如下：#includeusingnamespacestd;structgoodinfo floatp;/物品效益 floatw;/物品重量 floatX;/物品该放的数量 intflag;/物品编号;/物品信息结构体voidInsertionsort(goodinfogoods,intn) /插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序 intj,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列voidbag(goodinfogoods,floatM,intn) floatcu;inti,j;for(i=1;i=n;i+)goodsi.X=0;cu=M;/背包剩余容量for(i=1;in;i+)if(goodsi.wcu) / /若不超过容量，尽量增加物品 goodsi.X=1; cu-=goodsi.w;/确定背包新的剩余容量 else goodsi.X=0; for(j=2;j=n;j+)/*按物品编号做降序排列*/ goods0=goodsj; i=j-1; while(goods0.flaggoodsi.flag) goodsi+1=goodsi; i-; goodsi+1=goods0; cout最优解为:endl;for(i=1;i=n;i+)cout第i件物品要放:; coutgoodsi.Xendl;voidmain()cout|-运用贪心法解背包问题-|endl;intj,n;floatM;goodinfo*goods;/定义一个指针while(j) coutn;goods=newstructgoodinfon+1;/coutM;coutendl;inti;for(i=1;i=n;i+)goodsi.flag=i;cout请输入第igoodsi.w;cout请输入第igoodsi.p; goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n);coutpresstorunagianendl;coutpresstoexitj; 七、运行结果：上述结果显示:贪心算法不是总是最优