算法实验报告(可以参考)Word文档下载推荐.docx
《算法实验报告(可以参考)Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《算法实验报告(可以参考)Word文档下载推荐.docx（9页珍藏版）》请在冰点文库上搜索。
378.560000
1268235.895000
1267857.335（5次）
2用贪心算法实现背包问题，按下表格式列出其中的五种情况，其中物品个数、背包容量、物品重量和物品价值要随机产生。
物品个数
N（自己输入）
背包容量C（设置为随机产生的重量的三分之一
加一）
物品重量Wi（随机产生，重量产生的在10以内
物品价值Vi（随机产生，价值在100
）以内）
最优值
最优解
所需时间
（ms）（只计算一次）
5
6．6667
见图一：
221.7333
见图二：
3.000000
10
20.0000
见图三：
337.0000
见图四：
8.000000
15
28.0000
见图五：
见图五:
524.8571
见图六：
21.000000
20
39.6667
见图七：
689.8000
见图八：
46.000000
25
48.0000
见图九：
800.4286
见图十：
48.000000
附图：
图一 图二
图三 图四
图五 图六
图七 图八
图九 图十
附件：
源代码：
1.快速排序和插入排序所需时间的比较
#include<
stdio.h>
#include<
stdlib.h>
time.h>
sys\timeb.h>
inta[1000000];
intb[1000000];
voidQuickSort（intlow,inthigh）
{
longi,j;
intx;
i=low;
j=high;
x=a[i];
while（i<
j）
while（a[j]>
=x&
&
i<
j） j--;
a[i]=a[j];
while（a[i]<
j） i++;
a[j]=a[i];
}
a[i]=x;
if（low<
（i-1））
QuickSort（low,i-1）;
if（high>
（j+1））
QuickSort（j+1,high）;
voidBinaryInsertSort（intlength）
intlow,high,mid;
int i,j,m;
//m为保存待插入的元素
for（i=1;
length;
i++）
m=b[i];
low=0;
high=i-1;
//设置初始区while（low<
=high）
mid=（low+high）/2;
if（m>
=b[mid]）
low=mid+1;
else
high=mid-1;
for（j=i-1;
j>
=high+1;
j--）//high为插入位置
b[j+1]=b[j];
//后移元素，留出插入的空位
b[high+1]=m;
//将元素插入正确的位置
voidmain（）
time_tstart,finish;
//time_t相当于long
doublebetween_time1,between_time2,between_time;
//1表示快速排序所需时间，2表示插入排序所需时间，between_time表示两种排序之间的差值
struct_timebtimebuffer1,timebuffer2;
intstartm,finishm;
doubletotal1=0,total2=0;
//1表示规模为N时，快速排序所需的累计时间，2表示规模为N是，插入排序所需的累计时间
intN,i,j;
//N表示问题规模
printf（"
\n请输入问题的规模：
"
）;
scanf（"
%d"
&
N）;
//对一堆数据进行排序，排序1000次,求其排序的平均时间for（i=0;
1000;
srand（（unsigned）time（NULL））;
//对每次的排序进行设置随机种子（即编号）for（j=0;
j<
N;
j++）
a[j]=rand（）;
b[j]=a[j];
//快速排序
_ftime（&
timebuffer1）;
//计算当前时间startm=timebuffer1.millitm;
//start=timebuffer1.time;
QuickSort（0,N-1）;
//printf（"
\n快速排序之后的数据为:
//for（i=0;
//{
// printf（"
%d "
a[i]）;
//}
finishm=timebuffer1.millitm;
finish=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插入排序之后的数据为:
//{
b[i]）;
finishm=timebuffer2.millitm;
finish=timebuffer2.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.6f\n\n"
between_time）;
2.背包问题
doubleW[100];
//重量doubleV[100];
//价值
doubleunit_price[100];
//表示每个物品的单价
voidQuickSort（intlow,inthigh）//对单价进行排序
doublex;
doublew,v;
x=unit_price[i];
w=W[i];
v=V[i];
while（i<
while（unit_price[j]>
unit_price[i]=unit_price[j];
W[i]=W[j];
//将重量，价值和单价的下标始终统一V[i]=V[j];
while（unit_price[i]<
unit_price[j]=unit_price[i];
W[j]=W[i];
V[j]=V[i];
unit_price[i]=x;
W[i]=w;
V[i]=v;
if（low<
（i-1））QuickSort（low,i-1）;
if（high>
（j+1））QuickSort（j+1,high）;
doublebetween_time;
struct_timebtimebuffer;
intN,i,j;
//N表示物品个数
doublesum=0,C,best_value=0;
\n请输入物品个数（假设不超过100）：
//随机产生物品重量以及价值srand（（unsigned）time（NULL））;
\n随机产生的物品重量,价值：
for（i=0;
W[i]=rand（）%10+1;
//重量产生的在10以内
V[i]=rand（）%100+1;
//价值在100以内printf（"
\n%6.4lf,%6.4lf"
W[i],V[i]）;
for（i=0;
i++）sum=sum+W[i];
C=sum/3+1;
//将背包容量设为所有物品重量的三分之一加1
\n\n该背包的容量为：
%6.4lf"
C）;
//从此处开始计算时间
timebuffer）;
startm=timebuffer.millitm;
start=timebuffer.time;
i++）unit_price[i]=V[i]/W[i];
//对单价进行排序（升序）for（i=N-1;
i>
=0;
i--）
if（C<
=W[i]）
break;
else
C=C-W[i];
\n\n最优解如下：
\n物品重量 物品价值"
for（j=N-1;
i;
j--）
\n%6.4lf %6.4lf"
W[j],V[j]）;
best_value=best_value+V[j];
C,C*unit_price[i]）;
best_value=best_value+C*unit_price[i];
\n\n最优值为：
best_value）;
//计算时间结束
finishm=timebuffer.millitm;
finish=timebuffer.time;
between_time=difftime（finish,start）*1000+finishm-startm;
\n\n该次所需时间为：
%6.8lf\n\n"
升级会员 