算法分析与设计上机实验

算法分析与设计实验报告实验：0/1背包问题实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。实验题：有五个物品，其重量分别为（3,2,1,4,5），物品的价值分别为（25,20,15,40,50），背包容量为6，写出求解过程。"0-1"背包问题的贪心算法"0-1"背包问题的动态规划算法"0-1"背包问题的回溯算法实验步骤：1.理解算法思想和问题要求；2.编程实现题目要求；3.上机输入和调试自己所编的程序；4.验证分析实验结果；5.整理出实验报告。实验程序："0-1"背包问题的贪心算法#include<iostream>usingnamespacestd;intmain(){ inti,j,a,b,Cr=6,W=0,V=0; floatper[20]; intw[]={3,2,1,4,5},v[]={25,20,15,40,50}; cout<<"物品重量为："; for(i=0;i<5;i++) { cout<<w[i]<<","; } cout<<endl<<"物品价值为："; for(i=0;i<5;i++) { cout<<v[i]<<","; } //按照价值大小降序排序 for(i=4;i>=0;i--) { for(j=0;j<i;j++) if(v[i]>v[j]){ a=v[i]; v[i]=v[j]; v[j]=a; b=w[i]; w[i]=w[j]; w[j]=b; } } cout<<endl<<"方法一，价值最大原则："<<endl<<"按价值大小排序后："<<endl<<"物品重量为："; for(i=0;i<5;i++) { cout<<w[i]<<","; } cout<<endl<<"物品价值为："; for(i=0;i<5;i++) { cout<<v[i]<<","; } cout<<endl<<"放入背包的物品为："; //把物品按要求放入背包 for(i=0;i<5;i++) { while(Cr>=w[i]&&Cr>=0) { W=W+w[i]; Cr=Cr-w[i]; V=V+v[i]; a=i; cout<<w[a]<<","; } } cout<<endl<<"结果为：背包重量为："<<W<<",背包价值为："<<V<<endl; cout<<endl<<"方法二，重量最轻原则："<<endl<<"按重量大小排序后："<<endl<<"物品重量为："; //按照重量大小升序排序， for(i=4;i>=0;i--) { for(j=0;j<i;j++) if(v[i]<v[j]){ a=v[i]; v[i]=v[j]; v[j]=a; b=w[i]; w[i]=w[j]; w[j]=b; } } for(i=0;i<5;i++) { cout<<w[i]<<","; } cout<<endl<<"物品价值为："; for(i=0;i<5;i++) { cout<<v[i]<<","; } cout<<endl<<"放入背包的物品为："; Cr=6,W=0,V=0; //把物品按要求放入背包 for(i=0;i<5;i++) { if(Cr>=w[i]&&Cr>=0) { W=W+w[i]; Cr=Cr-w[i]; V=V+v[i]; a=i; cout<<w[a]<<","; } } cout<<endl<<"结果为：背包重量为："<<W<<",背包价值为："<<V<<endl; cout<<endl<<"方法三，单位重量价值最大原则："<<endl<<"按单位重量价值大小排序后："<<endl<<"物品重量为："; for(i=0;i<5;i++) { per[i]=v[i]/w[i]; }//如果单位重量价值相等，按照重量大小降序排序 for(i=4;i>=0;i--) { for(j=0;j<i;j++) if(per[i]==per[j]&&w[i]>w[j]) { a=v[i]; v[i]=v[j]; v[j]=a; b=w[i]; w[i]=w[j]; w[j]=b; } } //按照单位重量价值大小降序排序 for(i=4;i>=0;i--) { for(j=0;j<i;j++) if(per[i]>per[j]){ a=v[i]; v[i]=v[j]; v[j]=a; b=w[i]; w[i]=w[j]; w[j]=b; } } for(i=0;i<5;i++) { cout<<w[i]<<","; } cout<<endl<<"物品价值为："; for(i=0;i<5;i++) { cout<<v[i]<<","; } cout<<endl<<"放入背包的物品为："; Cr=6,W=0,V=0; //把物品按要求放入背包 for(i=0;i<5;i++) { if(Cr>=w[i]&&Cr>=0) { W=W+w[i]; Cr=Cr-w[i]; V=V+v[i]; a=i; cout<<w[a]<<","; } } cout<<endl<<"结果为：背包重量为："<<W<<",背包价值为："<<V<<endl; while(1) { ; }}"0-1"背包问题的动态规划算法#include<stdio.h>#defineMAX20intn,c,w[MAX],v[MAX],m[MAX][MAX]={0};voidknapsack(){inti,j;for(i=1;i<=n;i++)for(j=1;j<=c;j++) {m[i][j]=m[i-1][j]; if(j>=w[i-1]&&m[i-1][j-w[i-1]]+v[i-1]>m[i][j]) m[i][j]=m[i-1][j-w[i-1]]+v[i-1]; }}//显示所取的物品及其重量（其中一个解）//对数组m的最后一列检查来求解voiddisp(){ inti,j; i=n; while(m[i][c]==m[i-1][c])i--; while(i>0) { j=i-1; while(m[i][c]-m[j][c]!=v[i-1]&&j>0) j--; printf("%5d%5d\n",w[i-1],v[i-1]); i=j; }}voidmain(){ inti,j; printf("物品数:");scanf("%d",&n); printf("物品的重量与价值:\n"); for(i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]); printf("背包的总重量:\n");scanf("%d",&c); knapsack();disp(); printf("最大价值=%d\n",m[n][c]); for(i=0;i<=n;i++) { for(j=0;j<=c;j++) printf("%3d",m[i][j]); printf("\n");}}"0-1"背包问题的回溯算法#include<iostream>usingnamespacestd;voidinput(int*number,int*weight,int*price){inti,n;cout<<"包的容量:";cin>>weight[0];cout<<"物品数:";cin>>*number;cout<<"各物品的重量:";for(i=1;i<=*number;i++){cin>>weight[i];}cout<<"各物品的价值:";for(i=1;i<=*number;i++){cin>>price[i];}}voidbacktrack(intt,intn,int*weight,int*price,int*maxPrice,int*flag,int*nowWeight,int*nowPrice,int*x){inti;if(t>n){if(*nowWeight<=weight[0]&&*nowPrice>*maxPrice){*maxPrice=*nowPrice;flag[0]=0;for(i=1;i<=n;i++){if(x[i]){flag[++flag[0]]=i;}}}return;}else{for(i=0;i<=1;i++){x[t]=i;*nowWeight+=weight[t]*i;*nowPrice+=price[t]*i;backtrack(t+1,n,weight,price,maxPrice,flag,nowWeight,nowPrice,x);*nowWeight-=weight[t]*i;*nowPrice-=price[t]*i;}}}voidoutput(int*maxPrice,int*flag){inti;cout<<endl;cout<<"物品的最大价值为："<<*maxPrice<<endl;cout<<"选中的物品为：";for(i=1;i<=flag[0];i++){cout<<flag[i]<<"";}cout<<endl;}intmain(){inttemp1=0,temp2=-1,temp3=0,temp4=0;//这一行很重要!int*number=&temp1,weight[100],price[100];int*maxPrice=&temp2,flag[100],*nowWeight=&temp3,*nowPrice=&temp4,x[100];input(number,weight,price);backtrack(1,*number,weight,price,maxPrice,flag,nowWeight,nowPrice,x);output(maxPrice,flag);return0;}实验结果：1."0-1"背包问题的贪心算法2."0-1"背包问题的动态规划算法3."0-1"背包问题的回溯算法实验分析：1、“0-1”背包问题的贪心算法贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体上加以考虑，而是局部的最优解。贪心算法不是对所有问题都能得到整体最优解，但对相当广泛的问题能产生最优解的近似解。2、“0-1”背包问题的动态规划算法

动态规划过程的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。本题目中m[i][j]表示有i个物品，背包容量为j时的最优解，通过knapsack函数用来寻找最优解的值，自底向上地对每一个物品进行运算，并进行比较，然后选择，最后求出最优值。在通过disp函数用来输出动态规划法中的二维矩阵。3、“0-1”背包问题的回溯算法回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现