科技学院算法设计与分析实验报告.doc

华北电力大学科技学院实 验 报 告| 实验名称 算法设计与分析实验 课程名称 算法设计与分析 | 专业班级： 学生姓名： 学 号： 成 绩：指导教师： 实验日期： 华 北 电 力 大 学 科 技 学 院 实 验 报 告实验一 用动态规划方法求解0-1背包问题一、实验目的及要求1.理解动态规划算法的概念2.掌握动态规划算法的基本要素：最优子结构性质和重叠子问题性质3.掌握设计动态规划算法的步骤4.通过具体实例0-1背包问题学习动态规划算法设计策略二、所采用存储结构 数组存储结构三、实验步骤 1.问题：有n个物品U1，U2，U3.Un其体积和价值分别为Si和Vi，在限定背包的情况下，选取物品使背包价值最大。2.分析：不能放 SiC 能放 max（价值）放，不放最优子结构 设y1，y2，y3.yk是最优子结构，则y2.yk一定是C-S1的最优解设wij表示从前i件物品中选择若干件放入到容量为j的背包中所获得的最大价值例：C=9,S=2,3,4,5 V=3,4,5,7 代码：/0-1背包问题#include#define N 100int max(int a,int b)return ab?a:b;main()int c,sN,vN,n;printf(输入物品个数：n);scanf(%d,&n);printf(输入背包体积：n);scanf(%d,&c);printf(输入每个物品的体积：n);for(int a=0;an;a+)scanf(%d,&sa);printf(输入每个物品的价值：n);for(int b=0;bn;b+)scanf(%d,&vb);int wNN;int i,j;for(i=0;i=c;i+)w0i=0;for(i=0;i=n;i+)wi0=0;for(i=1;i=n;i+)for(j=1;j=si-1)wij=max(wi-1j,vi-1+wi-1j-si-1);elsewij=wi-1j;if(i=n & j=c)printf(背包可容纳最大价值为：%dn,wij);四、实验结果五、心得体会 通过0-1背包问题的求解，我了解了动态规划的方法，更熟悉的掌握了C+中地址的分配和数据的存储，更能熟悉的应用数组的输入存储和调用，更清晰的了解了二维数组的动态分配问题，知道了在程序中如何使用除main()以外的其他方法，并调用联系在一起，总之通过本次0-1背包问题的求解我掌握了更清晰的求解方法，并把之前的知识都回顾了，同时也提升了自己的动手能力和汇编能力，总而言之知这次实验我的收获很大。实验二 用贪心算法求解部分背包问题一、实验目的及要求1.理解贪心算法算法的概念2.掌握贪心算法的基本要素：最优子结构性质和贪心选择性质3.掌握设计贪心算法的步骤4.通过具体实例部分背包问题学习贪心算法设计策略二、所采用存储结构 数组存储结构三、实验步骤 1.问题：有n个物品U1，U2，U3.Un其体积和价值分别为Si和Vi，在限定背包的情况下，选取物品使背包价值最大。 2.分析：目标函数： 约束条件：贪心选择：选择单位价值最大的物品最优子结构： 设wW1，W2.Wk是全局最优解，则M=W1，W2.Wk-1，Wk且Sk=Sk-S一定是C-S的最优解。例：n=4，C=5，S=1，2，3，4，V=4，3，2，1代码：/部分背包问题#include#define N 100main()int n;double rN,xN,c,sN,vN;printf(输入物品个数：n);scanf(%d,&n);printf(输入背包体积：n);scanf(%lf,&c);printf(输入每个物品的体积：n);for(int a=0;an;a+)scanf(%lf,&sa);printf(输入每个物品的价值：n);for(int b=0;bn;b+)scanf(%lf,&vb);for(int i=0;in;i+)ri=(vi*1.0)/si;/对单位体积价值排序for(int z=0;zn;z+)for(int y=z;yn;y+)if(rz=ry)double temp1,temp2,temp3;temp1=ry;ry=rz;rz=temp1;temp2=vy;vy=vz;vz=temp2;temp3=sy;sy=sz;sz=temp3;double total;for(int j=0;jn;j+)xj=0;double Cu=c;j=0;total=0;while(jn)&(sjCu)xj=1;Cu=Cu-sj;total=total+vj;j+;if(jn)xj=Cu/sj;total=total+xj*vj;printf(产生的最大价值：%fn,total);四、实验结果五、心得体会首先这个实验，需要注意的点是背包问题与0-1背包不同，物品可以部分的放入背包中，所以思路也不一样，首先就是将物品按照单位质量价值排序，只这一点就有一点难度。难度在