算法实验报告01背包问题

河北工业大学计算机科学与软件学院算法分析与设计实验报告实验：0/1背包问题姓名：学号：班级：0-1背包问题的动态规划算法一、实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握0-1背包问题的三种算法，并分析其优缺点。三、实验程序：#includestdio.hintn=5;intw[]={0,3,2,1,4,5};intv[]={0,25,20,15,40,50};intx[5];intV[6][7];intC=6;voidmain(void){inti,j;for(i=0;i=n;i++)V[i][0]=0;for(j=0;j=C;j++)V[0][j]=0;for(i=1;i=n;i++){for(j=1;j=C;j++){if(jw[i])V[i][j]=V[i-1][j];else{if(V[i-1][j]V[i-1][j-w[i]]+v[i])V[i][j]=V[i-1][j];elseV[i][j]=V[i-1][j-w[i]]+v[i];}}}//以上构造动态规划表j=C;for(i=n;i0;i--){if(V[i][j]V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf(动态规划表如下：\n);for(i=0;i6;i++){for(j=0;j7;j++){printf(%8d,V[i][j]);}printf(\n);}printf(装入背包物品：\n);for(i=0;i6;i++)printf(%4d,x[i]);printf(\n背包取得最大值：\n);printf(%4d\n,V[n][C]);}三、实验结果：四、实验分析：这次实验用到的是动态规划法，0/1背包问题用动态规划法首先要构造动态规划表，用三个for语句实现；根据动态规划表每行的最大值变化确定每个元素的装入与否，逐步确定出装入背包的物品，背包容量的最大值也就是动态规划表最右下角。在本次实验中遇到了动态规划表构造紊乱的状况，经核查是因数组的初始位置0混淆成1造成的。0-1背包问题的贪心算法一、实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握0-1背包问题的三种算法，并分析其优缺点。三、实验程序：#includestdio.hvoidmain(void){intC=6;//背包容量6intn=5;//5个物品intw[]={3,2,1,4,5};//物品重量intv[]={25,20,15,40,50};//物品价值intx[]={0,0,0,0,0};//单位价值初始化intq[5];intm,i,j,p,vx,wx,k,ii;intV=0;//总价值初始化//计算单位价值printf(单位价值为：\n);for(m=0;m5;m++){q[m]=m;x[m]=v[m]/w[m];printf(x[%d]=%d\t,m,x[m]);}//冒泡排序for(i=0;i4;i++){for(j=0;j4-i;j++){if(x[j]x[j+1]){//交换单位价值p=x[j];x[j]=x[j+1];x[j+1]=p;//交换价值对应位置vx=v[j];v[j]=v[j+1];v[j+1]=vx;//交换重量对应位置wx=w[j];w[j]=w[j+1];w[j+1]=wx;//交换商品编号m=q[j];q[j]=q[j+1];q[j+1]=m;}}}printf(\n单位价值降序为：\n);for(i=0;i5;i++)printf(x[%d]=%d\t,i,x[i]);//装入背包for(i=0;in&&w[i]C;i++){if(w[i]=C){V+=v[i];C=C-w[i];}}k=i;if(C!=0){V+=v[i]*C/w[i];C=0;}for(ii=0;ii=k;ii++){printf(\n放入第%d个物品：\n物品的重量为：%d\n物品的价值为：%d\n背包剩余容量为：%d\n,q[ii]+1,w[ii],v[ii],C);}printf(\n总价值为：%d\t,V);}四、实验结果：五、实验分析：本次实验是以贪心算法解决背包问题，贪心算法要求出每个物品的单位价值，根据单位价值降序排列，再依次装入背包。当最后一个物品不能完全装入时，装入部分使背包容量为0。在本次实验中，遇到几个难题：1．保证物品按单位价值排列后依然能知道他的原始顺序位置，经过几番思考，决定设置一个数组来保存该物品的原始位置，在冒泡算法交换时同时交换物品编号；2．装入背包过程如何保证装入不完整物品，即背包剩余容量不能满足完全放入下一个物品。通过本次试验又熟悉了冒泡算法的应用，以及多重for循环的应用。0-1背包问题的回溯算法一、实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握0-1背包问题的三种算法，并分析其优缺点。三、实验程序：#includeiostream.h//定义min、max函数intmin(inta,intb){if(a=b)returnb;elsereturna;}intmax(inta,intb){if(a=b)returna;elsereturnb;}voidKnapsack(intv[6],intw[6],intc,intn,intm[6][6])//{intjmax=min(w[n]-1,c);for(intj=0;jjmax;j++)m[n][j]=0;for(intp=w[n];p=c;p++)m[n][p]=v[n];for(inti=n-1;i1;i--){jmax=min(w[i]-1,c);for(intj=0;j=jmax;j++)m[i][j]=m[i+1][j];for(intt=w[i];t=c;t++)m[i][t]=max(m[i+1][t],m[i+1][t-w[i]]+v[i]);}m[1][c]=m[2][c];if(c=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}voidTraceback(intm[6][6],intw[6],intc,intn,intx[6]){for(inti=1;in;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c]!=0)?1:0;}voidmain(){intn1=5;intc1=6;intw1[6]={0,3,2,1,4,5};intv1[6]={0,25,20,15,40,50};intt[6][6];intx1[6];intm=0;//cout请输入背包的容量：endl;//cinc1;cout0-1背包如下：endl;cout物品的重量分别为：endl;for(intp=1;p6;p++)coutw1[p];coutendl;cout物品的价值分别为：endl;for(intq=1;q6;q++)coutv1[q];coutendl;cout背包的容量为：c1endl;cout要选择的物品是:endl;Knapsack(v1,w1,c1,n1,t);//for(inti=1;i=n1;i++)coutv1[i]endl;Traceback(t,w1,c1,n1,x1);for(i=1;i=n1;i++)if(x1[i]==1){m+=v1[i];cout第i件物品endl;}cout最大总价值为：mendl;}四、实验结果：五、实验分析：本次实验用回溯法解决0/1背包问题，回溯法首先要建立0/1背包的解空间树，然后再回溯得出搜素空间，即解的范围，然后求出最佳答案。实验中先构造两个函数，Knapsack列出所有背包的解空间，Traceback对解空间进行搜索，得出答案。