算法实验报告Word文件下载.docx
《算法实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《算法实验报告Word文件下载.docx（22页珍藏版）》请在冰点文库上搜索。
>
n;
请输入真币和伪造硬币的重量"
t>
f;
for（i=0;
i<
size;
i++）//初始化数组
a[size]=0;
i++）
a[i]=t;
k=rand（）%n;
//随机产生假硬币的下标
a[k]=f;
随机产生的伪造硬币的位置"
k<
随机产生的硬币排列顺序"
//输出原始数组
{
a[i]<
"
;
if（（i+1）%20==0）
}
m=weight（0,n-1）;
if（m==-1）
没有伪造硬币"
else
伪造硬币的位置是"
m<
return0;
}
//称重函数m,n分别为数组的最小及最大下标，每次把硬币等分三堆
intweight（intm,intn）{
intj=0;
inti=0;
intsum1=0;
intsum2=0;
intsum3=0;
if（m>
=n）
return-1;
for（i=0;
（n-m+1）/3;
i++,j++）
sum1+=（a[m+j]）;
sum2+=（a[m+（n-m+1）/3+j]）;
sum3+=（a[m+2*（n-m+1）/3+j]）;
}
//数组元素个数除三余一的情况
if（（（n-m+1）%3）==1）
if（sum1==sum2）
if（sum1==sum3）
if（a[n]==a[n-1]）
return-1;
returnn;
m=m+2*（（n-m+1）/3）;
weight（m,n）;
m=m+（n-m+1）/3;
n=m+2*（（n-m+1）/3）-1;
n=m+（n-m+1）/3-1;
//数组元素个数除三余二的情况
else
if（（（n-m+1）%3）==2）
{
if（a[n]==a[n-2]）
if（a[n-1]==a[n-2]）
returnn-1;
m=m+2*（（n-m+1）/3）;
//数组元素个数被三整除的情况
实验结果
2.找零钱问题
源程序如下：
iostream.h>
{
intmoney,value,returns;
inttwenty_five,ten,five,one;
inti,j,k,l;
i=0;
j=0;
k=0;
l=0;
money=100;
value=33;
returns=money-value;
cout<
***应该找给孩子的钱是（美分）：
returns<
***请输入现有的25美分，10美分，5美分，1美分硬币的个数***"
cin>
twenty_five>
ten>
five>
one;
i=returns/25;
if（i<
=twenty_five）
returns-=25*i;
else
returns-=twenty_five*25;
i=twenty_five;
if（returns>
0）
j=returns/10;
if（j<
=ten）
returns-=10*j;
returns-=ten*10;
j=ten;
k=returns/5;
if（k<
=five）
returns-=5*k;
returns-=five*5;
k=five;
l=returns;
if（l<
=one）
returns-=l;
returns-=one;
l=one;
if（（returns=returns-（i*25+j*10+k*5+l））>
不好意思，现在没有足够的硬币！
***应找25美分的个数是：
***应找10美分的个数是：
j<
***应找5美分的个数是：
***应找1美分的个数是：
l<
return0;
实验结果：
实验二：
通过本实验加深对贪心算法、动态规划和回溯算法的理解。
掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"
0-1"
背包问题的三种算法，并分析其优缺点。
1."
背包问题的贪心算法
2."
背包问题的动态规划算法
3."
背包问题的回溯算法
四．1
背包问题的贪心算法源程序：
algorithm>
structgood//表示物品的结构体
doublep;
//价值
doublew;
//重量
doubler;
//价值与重量的比
}a[200];
doubles,value,m,result;
inti,n;
boolbigger（gooda,goodb）
returna.r>
b.r;
printf（"
----------背包问题之贪心算法------------------\n"
）;
输入物品个数:
scanf（"
%d"
&
n）;
//物品个数
输入物品的重量和价值：
for（i=0;
%lf%lf"
a[i].w,&
a[i].p）;
a[i].r=a[i].p/a[i].w;
sort（a,a+n,bigger）;
//调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心
输入背包的容量；
%lf"
m）;
//读入包的容量m
s=0;
//包内现存货品的重量
value=0;
//包内现存货品总价值
result=0;
n&
&
（s+a[i].w）<
=m;
{value+=a[i].p;
s+=a[i].w;
result=value*s;
背包内物品总价值为：
%.2lf.\n"
result）;
//输出结果
运行结果：
2
背包问题的动态规划算法源程序
iomanip>
vector>
voidKnapsack（vector<
int>
vct_v,vector<
vct_w,intc,intn）;
voidprint（vector<
v）;
voidprintarr（vector<
vector<
>
m,intp,intq）;
voidTraceback（vector<
m,vector<
voidmain（）
intmo=10;
vector<
vct_w;
vct_v;
intc,n,v,w;
***0-1背包问题之动态规划***"
***请输入物品个数***"
srand（（unsigned）time（NULL））;
vct_w.push_back（n）;
//第一个位置存放物品个数
for（inti=1;
=n;
w=rand（）%mo+1;
vct_w.push_back（w）;
vct_v.push_back（n）;
for（i=1;
v=rand（）%mo+10;
vct_v.push_back（v）;
***请输入背包容量***"
c;
***请输入物品重量***"
print（vct_w）;
***请输入物品价值***"
print（vct_v）;
Knapsack（vct_v,vct_w,c,n）;
v）
v.size（）;
cout<
setw（3）<
v[i]<
m,intp,intq）
=p;
for（intj=1;
=q;
j++）
cout<
m[i][j]<
}
vct_w,intc,intn）
m（n+1,vector<
（c+1））;
intjMax;
for（inti=0;
i++）//为每一行分配空间
jMax=vct_w[n]-1<
c?
vct_w[n]-1:
c;
for（intj=0;
=jMax;
m[n][j]=0;
for（j=vct_w[n];
=c;
m[n][j]=vct_v[n];
for（i=n-1;
i>
1;
i--）
intjMax=vct_w[i]-1<
c?
vct_w[i]-1:
for（intj=0;
m[i][j]=m[i+1][j];
for（j=vct_w[i];
m[i][j]=m[i+1][j]>
m[i+1][j-vct_w[i]]+vct_v[i]?
m[i+1][j]:
m[i+1][j-vct_w[i]]+vct_v[i];
m[1][c]=m[2][c];
if（c>
=vct_w[1]）
m[1][c]=m[1][c]>
m[2][c-vct_w[1]]+vct_v[1]?
m[1][c]:
m[2][c-vct_w[1]]+vct_v[1];
***m列表内容***"
printarr（m,n,c）;
Traceback（m,vct_w,c,n）;
x;
x.push_back（0）;
if（m[i][c]==m[i+1][c]）
x.push_back（0）;
else
{x.push_back
（1）;
c-=vct_w[i];
x.push_back（（m[n][c]）>
0?
1:
0）;
***动态规划所得的最优解为***"
x.size（）;
x[i]<
3
背包问题的回溯算法源程序
#include<
iomanip.h>
string.h>
intmin（intw,intc）
{inttemp;
if（w<
c）temp=w;
temp=c;
returntemp;
intmax（intw,intc）
inttemp;
if（w>
voidknapsack（intv[],intw[],intc,intn,int**m）//求最优值
intjmax=min（w[n]-1,c）;
=jmax;
m[n][j]=0;
for（intjj=w[n];
jj<
jj++）
m[n][jj]=v[n];
for（inti=n-1;
i--）{//递归部分
jmax=min（w[i]-1,c）;
m[i][j]=m[i+1][j];
for（intjj=w[i];
m[i][jj]=max（m[i+1][jj],m[i+1][jj-w[i]]+v[i]）;
=w[1]）
m[1][c]=max（m[1][c],m[2][c-w[1]]+v[1]）;
最优值：
m[1][c]<
for（intl=2;
l++）
m[l][j]<
setw（c-1）;
*******************************************"
inttraceback（int**m,intw[],intc,intn,intx[]）//回代，求最优解
得到的一组最优解如下:
if（m[i][c]==m[i+1][c]）x[i]=0;
else{x[i]=1;
c-=w[i];
x[n]=（m[n][c]）?
1:
0;
for（inty=1;
y<
y++）
setw（5）<
x[y];
returnx[n];
main（）
intn,c;
int**m;
------------------0-1背包问题之回溯--------------------"
请输入物品个数和重量上限:
n>
int*v=newint[n+1];
输入各物品价值（v[i]）:
v[i];
int*w=newint[n+1];
输入各物品重量（w[i]）:
for（intj=1;
w[j];
int*x=newint[n+1];
m=newint*[n+1];
//动态的分配二维数组
for（intp=0;
p<
n+1;
p++）
m[p]=newint[c+1];
knapsack（v,w,c,n,m）;
traceback（m,w,c,n,x）;
部分：
升级会员 