算法设计与分析实验报告.doc

算法设计与分析实验报告实验： 0/1背包问题一、 实验目的与要求：熟悉C/C+语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握0-1背包问题的三种算法，并分析其优缺点。三、实验题：1. 0-1背包问题的贪心算法2. 0-1背包问题的动态规划算法3. 0-1背包问题的回溯算法四、实验步骤：1. 理解算法思想和问题要求；2. 编程实现题目要求；3. 上机输入和调试自己所编的程序；4. 验证分析实验结果；5. 整理出实验报告。五、实验程序：贪心算法：/ 贪心算法.cpp : 定义控制台应用程序的入口点。/#include stdafx.hint _tmain(int argc, _TCHAR* argv)return 0;#includeusing namespace std;struct goodinfo float weight; /物品重量 float value; /物品价值 float vperw; /物品该放的数量 int flag;/是否装入 int order;/物品序号;void Insertionsort1(goodinfo goods,int n) for(int j=2;jgoodsi.vperw)goodsi+1=goodsi;i-;goodsi+1=goods0; /按物品价值重量比值做降序序排列void Insertionsort2(goodinfo goods,int n) for(int j=2;j=n;j+) goods0=goodsj;int i=j-1;while(goods0.weightgoodsi.weight)goodsi+1=goodsi;i-;goodsi+1=goods0; /按物品重量做升序排列void Insertionsort3(goodinfo goods,int n) for(int j=2;jgoodsi.value)goodsi+1=goodsi;i-;goodsi+1=goods0; /按物品价值做降序排列void bag(goodinfo goods,float M,int n) float cu,sum=0; int i; for(i=1;i=n;i+) goodsi.flag=0; cu=M; /背包剩余容量 for(i=1;i=n;i+) coutgoodsi.weight; if(goodsi.weight=cu)/当该物品重量大与剩余容量跳出 goodsi.flag=1; cu=cu-goodsi.weight;/确定背包新的剩余容量 sum+=goodsi.value; cout最优解为:endl; for(i=1;i=n;i+) cout物品goodsi.order装入:goodsi.flagendl; cout总价值为：sumendl ;void main() cout|-运用贪心法解背包问题-|endl; int n;/物品数量 float M;/背包容量 goodinfo *goods;/定义一个指针 coutn; goods=new struct goodinfo n+1; coutM; coutendl; for(int i=1;i=n;i+) goodsi.order=i; cout请输入第igoodsi.weight; cout请输入第igoodsi.value; goodsi.vperw=goodsi.value/goodsi.weight;/得出物品的价值重量比 coutendl; Insertionsort1(goods,n); cout按照价值重量比值得策略的贪心算法endl; bag(goods,M,n); Insertionsort2(goods,n); cout按照重量最轻的贪心策略endl; bag(goods,M,n); Insertionsort3(goods,n); cout按照价值最大优先的贪心策略endl; bag(goods,M,n);运行结果：动态规划：/ 动态规划.cpp : 定义控制台应用程序的入口点。/#include stdafx.hint _tmain(int argc, _TCHAR* argv)return 0;#includeint Va2040,x20;int C;int max(int i,int j)if(ij)return i;elsereturn j;int knapsack(int n,int w,int v)for(int i=0;i=n;i+)Vai0=0;for(int j=0;j=C;j+)Va0j=0;for(int i=1;i=n;i+)for(int j=1;j=C;j+)if(j0;i-)if(VaijVai-1j)xi=1;j=j-wi;elsexi=0;printf(最优解为：);for(int i=1;i=n;i+)printf(物品%d装入:%dn,i,xi);return VanC;void main()int n,m;int value20,weight20;value0=0;weight0=0;printf(输入物品数量n); scanf(%d,&n);printf(输入各物品的重量及价值n);for(int i=1;i=n;i+)printf(物品%d的重量为：,i); scanf(%d,&weighti); printf(物品%d的价值为：,i); scanf(%d,&valuei);printf(输入背包最大容量n); scanf(%d,&C);m=knapsack(n,weight,value);printf(最大价值为:%dn,m); 运行结果：回溯算法：/ 回溯算法.cpp : 定义控制台应用程序的入口点。/#include stdafx.hint _tmain(int argc, _TCHAR* argv)return 0;#include using namespace std;int min(int a,int b)if(a=b) return b;else return a;int max(int a,int b)if(a=b) return a;else return b;void Knapsack(int v6,int w6,int c,int n,int m66)int jmax=min(wn-1,c);for(int j=0;jjmax;j+)mnj=0;for(int p=wn;p1;i-)jmax=min(wi-1,c);for(int j=0;j=jmax;j+)mij=mi+1j;for(int t=wi;t=w1)m1c=max(m1c,m2c-w1+v1);void Traceback(int m66,int w6,int c,int n,int x6)for(int i=1;in;i+)if(mic=mi+1c) xi=0;else xi=1;c-=wi;xn=(mnc!=0)?1:0;void main()int n1=5;int c1=6;int w16=0,3,2,1,4,5;int v16=0,25,20,15,40,50;int t66;int x16;int m=0;/*cout请输入背包的容量：c1;cout0-1背包问题是：endl;cout物品的重量分别为：endl;for(int p=1;p6;p+) coutw1p ;coutendl;cout物品的价值分别为：endl;for(int q=1;q6;q+) coutv1q ;coutendl;cout背包的容量为：c1endl;*/cout要选择的物品是:endl;Knapsack(v1,w1,c1,n1,t);for(int i=1;i=n1;i+)coutv1iendl;Traceback(t,w1,c1,n1,x1);for(int i=1;i=n1;i+)if(x1i=1) m+=v1i; cout第i件物品装入endl;elsecout第i件物品不装入endl;cout背包总容量：mendl;运行结果：六、实验分析动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。贪心法求解的问题的特征：（1）最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。（2）贪心选择性质所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择。回溯法的基本思想回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点