背包和SubsetSum问题的近似解.ppt_第1页
背包和SubsetSum问题的近似解.ppt_第2页
背包和SubsetSum问题的近似解.ppt_第3页
背包和SubsetSum问题的近似解.ppt_第4页
背包和SubsetSum问题的近似解.ppt_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、背包问题的近似解,一、背包问题的数学描述,给定整数C和2个整数序列(s1,s2,sn) (p1,p2,pn) 。 s1,s2,sn以非递增的顺序排列。设N=(1,2,n)为下标集,求：,受限于：,问题的简化版,给定整数C和整数序列(s1,s2,sn) ，设(1,2,n)为下标集,求:,受限于：,二、背包问题的简单近似算法,sKnapk(C,S,take) int maxSum,sum; indexSet T = new IndexSet; int j; take =; maxSum = 0; for each subset TN with at most k elements: sum =iT

2、 si;,if (sumC) for each j not in T: if (sum+ sj C) sum+= sj; T=Tj; if (maxsumsum) maxsum=sum; copy fields of T into take. return maxSum;,三、例,C=110，整数序列为(54,45,43,29,23,21,14,1) ，则最优解为(43,29,23,14,1) 求解过程中，k=0和1的情况见P579,四、相关定理,定理13.12,定理：对k0,算法sKnapk 做 O(knk+1)次运算； sKnap0做(n) 次运算。所以对k0 ，sKnapk P 证明：

3、N包含j个元素的子集共有Cnj个，所以外循环做,次运算。,因为Cnjnj，所以:,加上内循环的至多n次的复杂性，算法的复杂性为O(knk+1+n)。,定理13.13,定理：对k0,RsKnapk (m) 和SsKnapk (n)在最坏情况下至多为1+1/ k。,设输入I为(s1,s2,sn) ，opt(I )=m(最优解情况下，背包内所含物体的size总和)。 若 (si1,si2,sip) 是所得到的装填背包的最优解。 若pk,则最优解也应在近似算法的范围内。,若pk,则最优解(si1,si2,sip)以非递增的次序排列。 因为: m=si1+si2+sip 1jp sij m/j si(k+1) m/(k+1), 1jp sij m/j 根据近似算法，如果j 是最优解中k 之后第一个不能被加进val(sKnapk(I)的object: val(sKnapk(I)+sjCm val(sKnapk(I)

人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论