1、378.5600001268235.8950001267857.335（5 次）2 用贪心算法实现背包问题，按下表格式列出其中的五种情况，其中物品个数、背包容量、物品重量和物品价值要随机产生。物品个数N（自己输入）背包容量C（设置为随机产生的重量的三分之一加一）物品重量Wi（随机产生，重量产生的在 10 以内物品价值Vi（随机产生，价值在 100） 以内）最优值最优解所需时间（ms）（只计算一次）566667见图一：221.7333见图二：3.0000001020.0000见图三：337.0000见图四：8.0000001528.0000见图五：见图五:524.8571见图六：21.00000
2、02039.6667见图七：689.8000见图八：46.0000002548.0000见图九：800.4286见图十：48.000000附图：图一图二图三图四图五图六图七图八图九图十附 件 ： 源代码：1. 快速排序和插入排序所需时间的比较#include #includetime.hsystimeb.h int a1000000;int b1000000;void QuickSort（int low ,int high）long i,j; int x; i=low; j=high; x=ai; while（i=x&ij）j-;ai=aj; while（aij）i+;aj=ai;ai=x;
3、if（low（j+1）QuickSort（j+1,high）;void BinaryInsertSort（int length）int low,high,mid;inti,j,m;/m 为保存待插入的元素for（i=1;length;i+）m=bi; low=0;high=i-1;/设置初始区while（low=bmid）low=mid+1; elsehigh=mid-1;for（j=i-1;j=high+1;j-）/high 为插入位置bj+1=bj;/后移元素，留出插入的空位bhigh+1=m;/将元素插入正确的位置void main（）time_t start,finish;/time_
4、t 相当于 longdouble between_time1,between_time2,between_time;/1 表示快速排序所需时间，2 表示插入排序所需时间，between_time 表示两种排序之间的差值struct _timeb timebuffer1,timebuffer2; int startm,finishm;double total1=0,total2=0;/1 表示规模为 N 时，快速排序所需的累计时间，2 表示规模为 N 是，插入排序所需的累计时间int N,i,j;/N 表示问题规模printf（n 请输入问题的规模：）; scanf（%d,&N）;/对一堆数据进
5、行排序，排序 1000 次,求其排序的平均时间for（i=0;1000;srand（unsigned）time（NULL）;/对每次的排序进行设置随机种子（即编号） for（j=0;jN;j+）aj=rand（）;bj=aj;/快速排序_ftime（&timebuffer1）;/计算当前时间startm=timebuffer1.millitm;/ start=timebuffer1.time;QuickSort（0,N-1）;/ printf（n 快速排序之后的数据为:/for（i=0;/ /printf（%d,ai）;/ finishm=timebuffer1.millitm; finish
6、=timebuffer1.time;between_time1=difftime（finish,start）;/找出时间差between_time1=1000*between_time1+finishm-startm; total1=total1+between_time1;/ 插入排序timebuffer2）; startm=timebuffer2.millitm; start=timebuffer2.time; BinaryInsertSort（N）;/printf（n 插入排序之后的数据为:/,bi）; finishm=timebuffer2.millitm; finish=timebu
7、ffer2.time; between_time2=difftime（finish,start）;between_time2=between_time2*1000+finishm-startm;/ total2=total2+between_time2;n 快速排序的时间（以毫秒为单位）是：%6.6f,total1/1000）;n 插入排序的时间（以毫秒为单位）是：,total2/1000）; between_time=total1/1000-total2/1000;n 两种排序相差的时间是：%6.6fnn,between_time）;2. 背包问题double W100;/重量double
8、V100;/价值double unit_price100;/表示每个物品的单价void QuickSort（int low ,int high）/对单价进行排序 double x; double w,v;x=unit_pricei; w=Wi;v=Vi;while（iunit_pricei=unit_pricej;Wi=Wj;/将重量，价值和单价的下标始终统一Vi=Vj;while（unit_priceiunit_pricej=unit_pricei; Wj=Wi;Vj=Vi;unit_pricei=x;Wi=w;Vi=v;if（low（j+1） QuickSort（j+1,high）; do
9、uble between_time;struct _timeb timebuffer; int N,i,j;/N 表示物品个数double sum=0,C,best_value=0;n 请输入物品个数（假设不超过 100）：/随机产生物品重量以及价值srand（unsigned）time（NULL）;n 随机产生的物品重量,价值： for（i=0;Wi=rand（）%10+1;/重量产生的在 10 以内Vi=rand（）%100+1;/价值在 100 以内printf（n%6.4lf , %6.4lf,Wi,Vi）;for（i=0;i+） sum=sum+Wi;C=sum/3+1;/将背包容量
10、设为所有物品重量的三分之一加 1nn 该背包的容量为：%6.4lf,C）;/从此处开始计算时间timebuffer）; startm=timebuffer.millitm; start=timebuffer.time;i+） unit_pricei=Vi/Wi;/对单价进行排序（升序） for（i=N-1;i=0;i-）if（C=Wi）break;elseC=C-Wi;nn 最优解如下：n 物品重量物品价值 for（j=N-1;i;j-）n%6.4lf%6.4lf,Wj,Vj）; best_value=best_value+Vj;,C,C*unit_pricei）;best_value=best_value+C*unit_pricei;nn 最优值为：,best_value）;/计算时间结束 finishm=timebuffer.millitm; finish=timebuffer.time;between_time=difftime（finish,start）*1000+finishm-startm;nn 该次所需时间为：%6.8lfnn
