算法实验报告01背包问题

河北工业大学计算机科学与软件学院算法分析与设计实验报告实验：0/1背包问题姓名：学号：班级："0-1"背包问题的动态规划算法实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。实验程序：#include"stdio.h"intn=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(j<w[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]; else V[i][j]=V[i-1][j-w[i]]+v[i]; } } }//以上构造动态规划表 j=C; for(i=n;i>0;i--) { if(V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } printf("动态规划表如下：\n"); for(i=0;i<6;i++) { for(j=0;j<7;j++) { printf("%8d",V[i][j]); } printf("\n"); } printf("装入背包物品：\n"); for(i=0;i<6;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"背包问题的三种算法，并分析其优缺点。实验程序：#include"stdio.h"voidmain(void){ intC=6;//背包容量6 intn=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;m<5;m++) { q[m]=m; x[m]=v[m]/w[m]; printf("x[%d]=%d\t",m,x[m]); } //冒泡排序 for(i=0;i<4;i++){ for(j=0;j<4-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;i<5;i++) printf("x[%d]=%d\t",i,x[i]); //装入背包 for(i=0;i<n&&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。在本次实验中，遇到几个难题：保证物品按单位价值排列后依然能知道他的原始顺序位置，经过几番思考，决定设置一个数组来保存该物品的原始位置，在冒泡算法交换时同时交换物品编号；装入背包过程如何保证装入不完整物品，即背包剩余容量不能满足完全放入下一个物品。通过本次试验又熟悉了冒泡算法的应用，以及多重for循环的应用。"0-1"背包问题的回溯算法实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。实验程序：#include<iostream.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;j<jmax;j++) m[n][j]=0; for(intp=w[n];p<=c;p++) m[n][p]=v[n]; for(inti=n-1;i>1;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;i<n;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; //cin>>c1; cout<<"0-1背包如下："<<endl; cout<<"物品的重量分别为："<<endl; for(intp=1;p<6;p++) cout<<w1[p]<<""; cout<<endl; cout<<"物品的价值分别为："<<endl; for(intq=1;q<6;q++) cout<<v1[q]<<""; cout<<endl; cout<<"背包的容量为："<<c1<<endl; cout<<"要选择的物品是:"<<endl; Knapsack(v1,w1,c1,n1,t); //for(inti=1;i<=n1;i++)cout<<v1[i]<<endl; Traceback(t,w1,c1,n1,x1); for(i=1;i<=n1;i++) if(x1[i]==