实验贪心算法设计信科

1、实验序号：9学号23姓名专业、班10信科班实验地点318指导教师惠云时间2013.5.30宁夏师范学院数学与计算机科学学院算法分析与设计实验报告实验项目名称：贪心算法设计一、实验目的及要求(1) 掌握贪心算法的基本思想和组成要素；掌握使用贪心方法解决实际问题的基本方法和步骤；二、实验设备(环境)及要求1、环境要求：硬件：PC(PII以上，128M以上内存)、因特网接入；软件：WindowsXP操作系统、VC+6.0编程环境。2、实验要求：(1) 独立完成实验，源代码书写规范；(2) 程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确；(3) 实验完成后必须有实验结果的分析及本次实验的

2、总结。三、实验内容与步骤1、设计求解背包问题的程序，并将装入背包的物品的最大价值及最优解在屏幕上显示#include<stdio.h>#definemaxnumber20typedefstructnodefloatw;floatv;inti;Object;floatfind(Objectwp,intn,floatM)floatxmaxnumber;inti;floatmaxprice=0;for(i=1;i<=n;i+)(xi=0.0;i=0;while(wpi.w<M)(xwpi.i=1;M=M-wpi.w;i+;xwpi.i=M/wpi.w;printf("

3、;解向量是:n");for(i=1;i<=n;i+)(printf("x%d=%f',i,xi);printf("n");for(i=0;i<n;i+)(maxprice=maxprice+wpi.v*xwpi.i;returnmaxprice;voidmain()(Objectwpmaxnumber;inti,j,n;floatC;intflag;floatmaxprice,temp;printf("请输入物品的种数:");scanf("%d”,&n);printf("请输入背包的重量

4、:");scanf("%f",&C);printf("n请输入物品的序号、重量和价值：")；for(i=0;i<n;i+)(scanf("%d",&wpi.i);scanf("%f",&wpi.w);scanf("%f",&wpi.v);printf("n输入的物品是：n");for(i=0;i<n;i+)(printf("%d",wpi.i);printf("%f",wpi.w);

5、printf("%f",wpi.v);printf("n");for(i=1;i<n;i+)(flag=0;for(j=n-1;j>=i;j-)(if(wpj-1.v/wpj-1.w<wpj.v/wpj.w)(temp=wpj-1.i;wpj-1.i=wpj.i;wpj.i=temp;temp=wpj-1.w;wpj-1.w=wpj.w;wpj.w=temp;temp=wpj-1.v;wpj-1.v=wpj.v;wpj.v=temp;flag=1;if(flag=0)break;printf("n排序后的物品是：n"

6、);for(i=0;i<n;i+)(printf("%d",wpi.i);printf("%f",wpi.w);printf("%f',wpi.v);printf("n");maxprice=find(wp,n,C);printf("n物品的总价值为：%f',maxprice);2、设计求解最优装载问题的程序，并将能够装入轮船的集装箱的最大数量及在相应的装入序列在屏幕上显示。#include<stdio.h>#include<stdlib.h>#defineN3intm

7、ain()(inttN,wN,n,c,m,i,j=0,sum=0;intmin;intmax=0,weight=0;printf("请输入轮船的载重量c:n");scanf("%d”,&c);printf("请输入可以装入的集装箱的数目n:n");scanf("%d",&n);printf("请输入各集装箱的重量:n");for(i=0;i<N;i+)scanf("%d",&wi);for(i=1;i<=N;i+)for(j=i+1;j<=n;

8、j+)if(wi>wj)inttem;tem=wj;wj=wi;wi=tem;for(i=1;i<=N;i+)printf("%dn",wi);printf("n");n=i-1;printf("最优装载情况为:");for(i=1;i<=N;i+)printf("%d",wi);printf("装入轮船的集装箱序列为:");for(i=1;i<=N;i+)sum+=wi;if(sum<=c)printf("%d",wi);printf("装入的集装箱的最大重量为:%dn",sum);四、实验结果与数据处理1.背包问题的结果:障输入物品的序号、玮号和价值三±20sP20±G033&120输-分的物晶是:=±20_660000Z20-019196*00331H_序后的物品是;1kfi,nFiFmnoX.tjididididid±-2&.00000033B_000000巨号7星kE11=1_B0B000X2J=1.nnnnnnxcs1=0.333333物品的重价值关n200-000000Px'css