第3章动态规划3-4节-0-1背包问题_第1页
第3章动态规划3-4节-0-1背包问题_第2页
第3章动态规划3-4节-0-1背包问题_第3页
第3章动态规划3-4节-0-1背包问题_第4页
第3章动态规划3-4节-0-1背包问题_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

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

文档简介

1、1，3.40-1背包问题，第3章动态规划(dynamic programming ).2，0-1背包问题，提供n种物品和背包。 物品I的重量是wi，其价值是vi，背包的容量是c。应该如何选择要放在背包中的东西，使要放在背包中的东西的总价值最大？0-1背包问题描述：给出的c 0，wi 0，VI 0，1 in .是n元向量(x1，x2，xn，)， 3，1 .最优子结构(最优原理)，最优原理：将(y1，y2，yn )作为(3.4.1)的最优解。 yn )不是其最佳解。 显然有vizi viyi (i=2，n )，w1y1 wizi c因此将v1y1 vizi (i=2，n) viyi，(i=1，n

2、)的不符点.4，2 .递归关系，给出的0-1背包问题的子问题，的最佳值设为m(i，n ) 可以选择的东西是I，i 1，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择，可以选择， 可以制作注：(3-4-3)式，此时的背包容量为j，可选择的为I。 此时，在确定了xi之后，问题是两种状态之一的：背包的剩馀容量是j，没有产生任何增益的剩馀容量j-wi的增益值从vi增加的. n推到i 1，从而I计算出最佳值m(i，j) (i

3、=n，1 )。 m(1，c )是最佳值。 然后，利用反蕾丝花边法Traceback，求出最佳解xi中的I，c的整型数据，3 .从算法复杂度分析： m(i，j )的递归公式可知，算法Knapsack需要O(nc )校正运算时间。 跟踪需要O(n )校正计算时间，而算法整体上需要O(nc )校正计算时间。 在背包容量c大的情况下，算法所需的校正计算时间多。 例如，对于c2n而言，算法要求(n2n )校正运算时间。 6、4 .算法描述、模板语音密钥(类型v、输入w、输入c、输入n、类型* * m )输入jmax=min (wn1JC/mnj=VN； 英国足球甲级联赛； i1； 小时(wi-1、c )； for (英寸j=0； 最大值(mi1j、mi 1j-wi vi )。 /利益值为vi /、背包问题的动态修正计划算法Knapsack如下：7、4 .算法描述、m1c=m2c； if (c=w1) m1c=最大(m1c、m2c-w1 v1)。 模板/

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

温馨提示

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

最新文档

评论

0/150

提交评论