四、源程序及实验结果
程序代码如下： #include
int n; //n用于存放物品的数目
float A[1024]; //数组A[]存放待分类元素（在本问题中是指物品的单位容量增量） float X[1024]; //数组X[]存放解向量，即各个物品在背包中的存放情况，0= void interchangeP(int i,int j) //交换两整型效益的位置 { int t; t=P[i]; P[i]=P[j]; P[j]=t; 11 } void interchangeW(int i,int j) //交换两整型容量的位置 { int t; t=W[i]; W[i]=W[j]; W[j]=t; } int partition(int m,int p) //用划分元素A[m]划分集合A(m:p-1),并返回划分元素定位后的位置 { int i; float v; v=A[m]; i=m; while(1) { do { i++; }while(A[i]>v); do { p--; }while(A[p] if(i { interchange(i,p); //将A[i]与A[j]换位 interchangeP(i,p); //将P[i]与P[j]换位 interchangeW(i,p);//将W[i]与W[j]换位 } else break; } A[m]=A[p]; A[p]=v; interchangeP(m,p); interchangeW(m,p); return p; } void quicksort(int p,int q) //快速分类（本算法为递归算法） //将全局数组A(1:n)中的元素A[p],.....,A[q]按递减的方式分类{ int j; if(p j=partition(p,j); quicksort(p,j-1); quicksort(j+1,q); } } 12 void greedy_knapsa(int m)//背包问题的贪心算法 /*P(1:n)和W(1:n)分别含有按P[i]/W[i]>=P[i+1]/W[i+1]排序的n件物品的效益值和容量。 X(1:n)是解向量，m存放背包的容量，物品存放入背包有三种情况：未放、部分放入和全 部放入 */ { int cu,i; //cu用于存放背包的剩余容量 for(i=1;i<=n;i++) //将解向量初始化为0 X[n]=0; cu=m; for(i=1;i<=n;i++) //存放物品 { if(W[i]>cu)break; X[i]=1; cu-=W[i]; } if(i<=n)X[i]=(float)cu/W[i]; } void main() { int i,M; printf(\ scanf(\ //输入物品数目 printf(\ scanf(\ //输入背包容量 printf(\ for(i=1;i<=n;i++) //输入各物品的效益值 scanf(\ printf(\ for(i=1;i<=n;i++) //输入各物品的容量 scanf(\ for(i=1;i<=n;i++) //A[i]存放第i个物品的单位容量的效益增量 A[i]=(float)P[i]/W[i]; quicksort(1,n); //将效益集合和容量集合按物品单位容量的效益增量降序进行排序 greedy_knapsa(M); //执行贪心算法求出解向量 printf(\ for(i=1;i<=n;i++) //输出解向量 printf(\ printf(\} 运行结果如下图所示：(运行结果与理论结果一致) 13 五、结果分析 运行源程序后，先输入物品的数量，回车，再输入背包的容量，回车，然后依次输入各物品的效益值，回车，最后对应输入各物品的容量，回车，就会得到解向量（各物品存放情况，此时物品的顺序不一定与初始时一样）。不难看出，运行结果与理论值一致。 将物体事先按Pi/Wi的非增次序分好类，若物品分类的时间不算在内，则此算法所用时间为O（n）。 上机实验四 一、实验题目 贪心方法求带有限期的作业排序 二、算法介绍 度量标准的选择 pi作为量度。 以目标函数 i?J 量度标准：下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下得到最大增加的作业。 处理规则：按pi的非增次序来考虑这些作业。 ?三、程序流程图 四、源程序及实验结果 #include int p; int d; }job; job j1[N]={{0,0},{35,4},{30,2},{25,4},{20,3},{15,4},{10,8},{5,3}}; void back(job *ps,int m,int n) { int i; for(i=n;i>=m;i--) 14 { ps[i+1].p=ps[i].p; ps[i+1].d=ps[i].d; } } void main() { int t,t1,i,m;//t为所用时间,t1为预计时间 job j[N]; printf(\输出待处理的作业：效益值,截止期限\ printf(\ for(i=1;i printf(\ printf(\ } //初始化 j[0].p=j1[0].p; j[0].d=j1[0].d; j[1].p=j1[1].p; j[1].d=j1[1].d; t=1; for(i=2;i t1=t+1; if(j1[i].d>=t1 || j[i-1].d>=t1) { m=1; while(m<=t) { if(j1[i].d back(j,m,t); j[m].p=j1[i].p; j[m].d=j1[i].d; break; }else m++; 15