0-1背包问题(动态规划和贪心法实现).docxVIP

0-1背包问题(动态规划和贪心法实现).docx

  1. 1、本文档共12页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
0-1背包问题(动态规划和贪心法实现) 0-1背包问题(动态规划和贪心法实现) PAGE 0-1背包问题(动态规划和贪心法实现) 算法设计与分析实验报告 实验二 0-1背包问题 院系: 班级: 计算机科学与技术 学号: 姓名: 任课教师: 成绩: 湘 潭 大 学 2016年5月 PAGE PAGE 12 PAGE PAGE 0 实验二 0-1背包问题 实验内容 分别编程实现动态规划算法和贪心法求0-1背包问题的最优解,分析比较两种算法的时间复杂度并验证分析结果。 二.实验目的 1、掌握动态规划算法和贪心法解决问题的一般步骤,学会使用动态规划和贪心法解决实际问题; 2、理解动态规划算法和贪心法的异同及各自的适用范围。 三. 算法描述 /*动态规划 0-1背包问题算法如下*/ Templateclass Type Void Knapsack(Type v,int w,int c,int n,Type ** m){ int jMax = min(w[n] - 1,c); For(int j = 0;j = jMax;j++){ m[n][j] = 0; } For(int j = w[n];j = c;j++){ m[n][j] = v[n]; } For(int i = n- 1;i 1;i--){ jMax = min(w[i] - 1,c); For(int j = 0;j = jMax;j++) m[i][j] = m[i+1][j]; For(int j = 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] = max(m[1][c],m[2][c-w[1]]+v[1]); } Templateclass Type Void Traceback(Type**m,int w,int c,int n,int x) { for(int i =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]) 1:0; } 按上述算法Knapsack计算后m[1][c]给出所要求的0-1背包问题的最优解。相应的最优解可由算法Traceback计算如下。如果m[1][c] =m[2][c],则x1 = 0,否则x1 = 1。当x1=0时,由m[2][c]继续构造最优解。当x1 = 1时,由m[2][c-w1]继续构造最优解。以此类推,可构造出相应的最优解(x1,x2,...,xn),时间复杂性O(n2^n)。 /*贪心法 0-1背包问题*/ 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。 四. 算法实现 数据结构及函数说明 在该问题中物品质量W[n]和包所能承受的最大重量都是又用户自己任意定义的,在实现的过程中用到一个栈来实现。第i件物品的选择有两种可能:? ????????????????????????????i.??????????????物品i被选择,这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后。继续其余物品的选择;? ???????????????????????????ii.??????????????物品i不被选择,这种可能性仅当不包含物品i不满足条件的情况。?现以第一个物品为例,当物品1不被选择,则问题转变为相对于其他物品(2,3,……,n),背包重量仍然为maxweight;若物品1被选择,问题就变为关于最大背包重量为maxweight-w[1]的问题,现设r{maxweight,?maxweight-w[1]}为剩余重量的背包问题。 源程序代码 /*动态规划 0-1背包问题*/ #include #include int V[200][200]; int max(int a,int b) { if(a=b) return a; else return b; } int KnapSack(int n,int w[],int v[],int x[],int C) { int i,j; for(i=0;i=n;i++) V[i][0]=0; for(

文档评论(0)

认真对待 + 关注
官方认证
文档贡献者

该用户很懒,什么也没介绍

认证主体惠州市峰海网络信息科技有限公司
IP属地广东
统一社会信用代码/组织机构代码
91441300MA54K6GY5Y

1亿VIP精品文档

相关文档