欢迎来到天天文库
浏览记录
ID:47395345
大小:43.91 KB
页数:11页
时间:2019-07-09
《0-1背包问题动态规划和贪心法实现》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、标准文档算法设计与分析实验报告实验二0-1背包问题院系:班级:计算机科学与技术学号:姓名:任课教师:成绩:实用文案标准文档湘潭大学2016年5月实用文案标准文档实验二0-1背包问题一.实验内容分别编程实现动态规划算法和贪心法求0-1背包问题的最优解,分析比较两种算法的时间复杂度并验证分析结果。二.实验目的1、掌握动态规划算法和贪心法解决问题的一般步骤,学会使用动态规划和贪心法解决实际问题;2、理解动态规划算法和贪心法的异同及各自的适用范围。三.算法描述/*动态规划0-1背包问题算法如下*/TemplateVoidKnapsack(Typev,intw,intc,
2、intn,Type**m){intjMax=min(w[n]-1,c);For(intj=0;j<=jMax;j++){m[n][j]=0;}For(intj=w[n];j<=c;j++){m[n][j]=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(intj=w[i];j<=c;j++)min[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];If(c>=w[1])m[1][c]=
3、max(m[1][c],m[2][c-w[1]]+v[1]);实用文案标准文档}TemplateVoidTraceback(Type**m,intw,intc,intn,intx){for(inti=1;i4、m[2][c]继续构造最优解。当x1=1时,由m[2][c-w1]继续构造最优解。以此类推,可构造出相应的最优解(x1,x2,...,xn),时间复杂性O(n2^n)。/*贪心法0-1背包问题*/首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。四.算法实现1.数据结构及函数说明在该问题中物品质量W[n]和包所能承受的最大重量都是又用户自己任意定义的,在实现的过程中用到一个栈来实现5、。第i件物品的选择有两种可能: i. 物品i被选择,这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后。继续其余物品的选择; ii. 物品i不被选择,这种可能性仅当不包含物品i不满足条件的情况。 现以第一个物品为例,当物品1不被选择,则问题转变为相对于其他物品(2,3,……,n),背包重量仍然为maxweight;若物品1被选择,问题就变为关于最大背包重量为maxweight-w[1]的问题,现设r{maxwe6、ight, maxweight-w[1]}为剩余重量的背包问题。实用文案标准文档1.源程序代码/*动态规划0-1背包问题*/#include#includeintV[200][200];intmax(inta,intb){if(a>=b)returna;elsereturnb;}intKnapSack(intn,intw[],intv[],intx[],intC){inti,j;for(i=0;i<=n;i++)V[i][0]=0;for(j=0;j<=C;j++)V[0][j]=0;for(i=0;i<=n-1;i++)for(j=0;j<=C;j7、++)if(j=0;i--){实用文案标准文档if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf("选中的物品是:");for(i=0;i
4、m[2][c]继续构造最优解。当x1=1时,由m[2][c-w1]继续构造最优解。以此类推,可构造出相应的最优解(x1,x2,...,xn),时间复杂性O(n2^n)。/*贪心法0-1背包问题*/首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。四.算法实现1.数据结构及函数说明在该问题中物品质量W[n]和包所能承受的最大重量都是又用户自己任意定义的,在实现的过程中用到一个栈来实现
5、。第i件物品的选择有两种可能: i. 物品i被选择,这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后。继续其余物品的选择; ii. 物品i不被选择,这种可能性仅当不包含物品i不满足条件的情况。 现以第一个物品为例,当物品1不被选择,则问题转变为相对于其他物品(2,3,……,n),背包重量仍然为maxweight;若物品1被选择,问题就变为关于最大背包重量为maxweight-w[1]的问题,现设r{maxwe
6、ight, maxweight-w[1]}为剩余重量的背包问题。实用文案标准文档1.源程序代码/*动态规划0-1背包问题*/#include#includeintV[200][200];intmax(inta,intb){if(a>=b)returna;elsereturnb;}intKnapSack(intn,intw[],intv[],intx[],intC){inti,j;for(i=0;i<=n;i++)V[i][0]=0;for(j=0;j<=C;j++)V[0][j]=0;for(i=0;i<=n-1;i++)for(j=0;j<=C;j
7、++)if(j=0;i--){实用文案标准文档if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf("选中的物品是:");for(i=0;i
此文档下载收益归作者所有