——动态规划解决算法0-1背包问题实验报告(含源代码)

——动态规划解决算法0-1背包问题实验报告(含源代码)

ID:35497915

大小:86.45 KB

页数:7页

时间:2019-03-25

——动态规划解决算法0-1背包问题实验报告(含源代码)_第1页
——动态规划解决算法0-1背包问题实验报告(含源代码)_第2页
——动态规划解决算法0-1背包问题实验报告(含源代码)_第3页
——动态规划解决算法0-1背包问题实验报告(含源代码)_第4页
——动态规划解决算法0-1背包问题实验报告(含源代码)_第5页
资源描述:

《——动态规划解决算法0-1背包问题实验报告(含源代码)》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、西安邮电大学(计算机学院)课内实豔报告实验名称专业名称:计算机科学与技术班级:学生姓名:学号(8位):指导教师:实验日期:2014年5月9日实验目的及实验环境1•使用动态规划法和回溯法生成两个长字符串的最优化比对结果通过实际案例,领会算法的执行效率。2•掌握动态规划、贪心算法、回溯法、分支限界法的原理,并能够按其原理编程实现解决0-1背包问题,以加深对上述方法的理解。实验环境:VisualC++6.0二・实验内容1•设计一个O5八2)时间的算法,找出由n个数组成的序列的最长单调递增子序列2•将算法分析题3—1中算法的计算时间减

2、至O(nlogn)3•给定n种物品和一个背包。物品i的重量是,其价值为,背包容量为C。问应该如何选择装入背包的物品,使得装入背包中物品的总价值最大?三.方案设计1.动态规划的一个计算两个序列的最长公共子序列的方法如下:以两个序列X、Y为例子:设有二维数组f[ij]表示X的i位和Y的j位之前的最长公共子序列的长度,则有:f[ij]=max{f[i-l][j-1]+same(ij),f[i-lj],f[i,j-l]}其中,same(a,b)当X的第a位与Y的第b位相同时为“1”,否则为“0”。此时,二维数组中最大的数便是X和Y的最

3、长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。该算法的空间、时间复杂度均为O(nT),经过优化后,空间复杂度可为O(n)。核心代码:voidLCSL(intmjntn,int*x,int*y,intc[][N],intb[][N]){c[0][0]=0;intij;for(i=l;i<=m;i++)c[i][0]=0;for(i=l;i<=n;i++)c[0][i]=0;for(i=l;i<=m;i++)forQ=l;j<=m;j++){if(x[i]==y[j])b[i]OJ=l;}elseif(c[i-l][

4、j]>=c[i][j-l]){c[i]Ul=c[i-l][j];b[i]Ij]=2;}else{c[i]Ul=c[i]U-l];b[i]Ij]=3;}}cout«c[m][m]«endl;}voidLCS(inti,intj9int*x,intb[][N])if(i==Ollj==O)return;if(b[i][j]==l){LCS(Mj-l,x,b);for(inty=l;y

5、}elseLCS(iJ-l,x,b);}voidQuickSort(inta[],intp,intr){if(P

6、种物品,对l<=K=n第时物品的重量为正整数Wi价值为正整数Vi背包能承受的最大载重量为正整数C,现要求找出这n种物品的一个子集,使得子集中物品的总重量不超过C且总价值尽量大。动态规划算法描述:根据问题描述,可以将其转化为如下的约束条件和目标函数:寻找一个满足约束条件,并使目标函数式达到最大的解向量,使得,而且达到最大。(H背包问题具有最优子结构性质。假设是所给的问题的一个最优解,则是下面问题的一个最优解:。如果不是的话,设是这个问题的一个最优解,贝IJ,且。因此,,这说明是所给的(H背包问题比更优的解,从而与假设矛盾。按照上

7、面的情况,可以得到递推公式:设最优值为mGom(i,j)="max{m(i+XJ),m(i+l,j-)+}m(i+lj)J叫j>叫0intV[200][200];//Wi个物品装入容量为j的背包中获得的最大价值intmax(inta,intb){if(a>=b)returna;elsereturnb;}intKnapSack(intnjntw[],intv[],intx[],intC){intij;for(i=0;i<=n;i++)V[i][O]=O;for(j=0;j<=C;j++

8、)V[O][J]=O;for(i=0;i<=n-l;i++)for(j=0;j<=C;j++)if(j=

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。