- 1、本文档共110页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
* 3.6 0-1背包问题 问题描述 给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? * 0-1背包问题是一个特殊的整数规划问题。 求(x1,x2,…,xn)使目标函数 最大,其中c0, wi 0, vi 0, 1≤i≤n 0-1背包问题Knapsack(1,n,c) * 例:w = ( w1, w2, w3) = (2, 3, 4) v=(v1, v2, v3)=(2, 3, 4) 求Knapsack(1, 3, 6) 取x = (1, 0, 1)时,Knapsack(1,3,6) = (v1x1+v2x2+v3x3) = 1*1 + 2*0 + 5*1 = 6最大 用穷举法求解,时间复杂度为O(n2n) * 1、 最优子结构性质 证明:(反证法) 设(y1,y2,…,yn)是Knapsack(1,n,c)的一个最优解,则(y2,…,yn)是Knapsack(2,n,c-w1y1)子问题的一个最优解。若不然,设(z2,…,zn)是Knapsack(2,n,c-w1y1)的最优解,因此有 说明(y1,z2,…,zn)是Knap(1,n,c)的一个更优解,矛盾。 0-1背包问题Knapsack(1, n, c)满足最优性原理 * 2、 递归关系 设所给0-1背包问题的子问题记为Knapsack(i, n, j), j≤c(假设c, wi取整数) Knapsack(i, n, j)的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。 注:子问题的背包容量j在不断地发生变化 * 由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式如下: 临界条件 说明:当j<wi时,只有xi =0,则m(i,j)=m(i+1,j) 当j≥wi时,取xi =0时,为m(i+1,j) 取xi =1时,为m(i+1,j-wi)+ vi 3、 算法描述 void Knapsack (Type *v, int *w, int c, int n, Type **m) {//m[1][c]为最优值 int jMax=min(w[n]-1,c); //j≤jMax,即0≤j<wn; jjMax,即j≥wn for(int j=0;i=jMax;j++) m[n][j]=0; // 0≤jwn’ for(int j=w[n];i=c;j++) m[n][j]=v[n]; // j≥wn’ for(int i=n-1;i1;i--){ //i1表示对i=1暂不处理 i=1时只需求m[1][c] jMax=min(w[i]-1,c); for(int j=0;j=jMax;j++) // 0≤j<wi’ m[i][j]=m[i+1][j]; for(int j=w[i];j=c;j++) // j≥wi’ m[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]); } * void Traceback(Type **m, int *w, int c, int n, int *x) {//输出解X[ ] for (int i=1;in;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; } * 4、 计算复杂性分析 算法复杂度分析 从m(i,j)的递归式容易看出,算法需要O(nc)计算时间。当背包容量c很大时,算法需要的计算时间较多。 例:当c2n时,算法需要Ω(n2n)计算时间。 * 由m(i,j)的递归式容易证明,在一般情况下,对每一个确定的i(1
您可能关注的文档
- (苏教版)四年级数学下册课件_用计算机器计算.ppt
- 20150105第5版 第9章 关系查询处理和查询优化--提交版.pdf
- 20150105第5版 第10章 数据库恢复技术--提交版.pdf
- 20150105第5版 第11章 并发控制--提交版.pdf
- (新2010)绪论--电信运营组织管理.ppt
- 20150330上海高科技启动会.pdf
- (英文版)酒店餐饮部.pptx
- 20150422医患沟通专题讲座课件.pdf
- [] 计量经济学的统计学基础.pdf
- 、黄能坦老师主讲:课件制作与演示技巧3P.pdf
- 北师版七年级下册数学精品教学课件 第四章 三角形 1 认识三角形 集训课堂 测素质 与三角形有关的线段和角.ppt
- 《小王子》阅读测试题和答案.docx
- 华师版七年级下册数学精品教学课件 第10章 轴对称、平移与旋转 全章热门考点整合应用 全章热门考点整合应用.ppt
- 2025中国建材集团所属中建材石墨新材料公司招聘2人笔试参考题库附带答案详解.docx
- 2025中国国际工程咨询有限公司总部社会招聘20人笔试参考题库附带答案详解.docx
- 《小王子》测试题.docx
- 《小王子》阅读测试题答案.docx
- 《建筑工程测量》试题答案.docx
- 北师版七年级下册数学精品教学课件 第四章 三角形 5 利用三角形全等测距离 集训课堂 练素养 2.构造全等三角形的四大技法.ppt
- 2025中国中煤能源集团有限公司西南分公司(四川分公司)第二批招聘48人笔试参考题库附带答案详解.docx
最近下载
- 2025年第二批陕西延长石油集团所属单位社会招聘笔试参考题库附带答案详解.docx
- 英语交通大学欧洲文化渊源试卷.pdf
- 南京邮电大学2021-2022学年《财务管理学》期末考试试卷(B卷)含参考答案.docx
- 运动疗法及护理—持续性被动活动(康复护理技术).pptx
- 基层党支部党建工作方法优秀案例汇编(12篇,48页)范文.doc VIP
- 《民用建筑防爆设计规范》.pdf
- 15j403-1楼梯栏杆标准.docx VIP
- 《新编大学法语1》练习答案 参考译文(修订).pdf
- 临床踝泵运动技术规范团体标准要点.docx VIP
- 2024医院药剂科工作总结及下一步工作计划(必威体育精装版版).docx VIP
文档评论(0)