实验九 贪心算法设计 信科.doc

宁夏师范学院数学与计算机科学学院算法分析与设计实验报告实验序号：9 实验项目名称：贪心算法设计学号23姓名专业、班10信科班实验地点318指导教师惠云时间2013530一、实验目的及要求（1） 掌握贪心算法的基本思想和组成要素；（2） 掌握使用贪心方法解决实际问题的基本方法和步骤；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：Windows XP操作系统、VC+6.0编程环境。2、实验要求：(1) 独立完成实验，源代码书写规范；(2) 程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确；(3) 实验完成后必须有实验结果的分析及本次实验的总结。三、实验内容与步骤1、设计求解背包问题的程序，并将装入背包的物品的最大价值及最优解在屏幕上显示。#include#define maxnumber 20 typedef struct node float w; float v; int i; Object;float find(Object wp,int n,float M) float xmaxnumber; int i; float maxprice=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(解向量是：n); for(i=1;i=n;i+) printf(x%d=%f,i,xi); printf(n); for(i=0;in;i+) maxprice=maxprice+wpi.v*xwpi.i; return maxprice; void main() Object wpmaxnumber; int i,j,n; float C;int flag; float maxprice,temp; printf(请输入物品的种数:); scanf(%d,&n); printf(请输入背包的重量:); scanf(%f,&C); printf(n请输入物品的序号、重量和价值：); for(i=0;in;i+) scanf(%d,&wpi.i); scanf(%f,&wpi.w); scanf(%f,&wpi.v); printf(n输入的物品是：n); for(i=0;in;i+) printf( %d,wpi.i); printf( %f,wpi.w); printf( %f,wpi.v); printf(n); for(i=1;i=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); for(i=0;in;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#include #define N 3 int main() int tN,wN,n,c,m,i,j=0,sum=0; int min;int max=0,weight=0; printf(请输入轮船的载重量c:n);scanf(%d,&c); printf(请输入可以装入的集装箱的数目n:n); scanf(%d,&n); printf(请输入各集装箱的重量:n); for(i=0;iN;i+) scanf(%d,&wi); for(i=1;i=N;i+) for(j=i+1;jwj) int tem; tem=wj; wj=wi; wi=tem; for(i=1;i=N;i+)printf(%d n ,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背包问题的结果：2.结果：五、分析与讨论 1、分析求