算法设计与分析课件 39 01背包问题2_第1页
算法设计与分析课件 39 01背包问题2_第2页
算法设计与分析课件 39 01背包问题2_第3页
算法设计与分析课件 39 01背包问题2_第4页
算法设计与分析课件 39 01背包问题2_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

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

文档简介

算法设计与分析本节要点CONTENTS01背包问题2回溯法—01背包假设n个物品和1个购物车，每个物品i对应价值为vi，重量wi，购物车的容量为W（你也可以将重量设定为体积）。每个物品只有一件，要么装入，要么不装入，不可拆分。如何选取物品装入购物车，使购物车所装入的物品的总价值最大？根据题意，从n个物品中选择一些物品，相当于从n个物品组成的集合S中找到一个子集，这个子集内所有物品的总重量不超过背包容量，并且这些物品的总价值最大。S的所有的子集都是问题的可能解，这些可能解组成了解空间，在解空间中找总重量不价值最大的物品集作为最优解。超过背包容量且由问题的子集组成的解空间，称为子集树。回溯法—01背包（1）定义问题的解空间每个物品只有两种状态：装入和不装入。用变量xi表示第i种物品是否被装入，xi=1表示第i个物品装入背包；xi=0表示第i个物品不装入背包。该问题解的形式是一个n元组，且每个分量的取值为0或1。问题的解空间：{x1，x2，…，xi，…，xn}显约束：xi

=0或1，i=1，2，…，n。回溯法—01背包（2）确定解空间的组织结构问题的解空间描述了2n种可能解，也可以说是n个元素组成的集合所有子集个数。例如3个物品的01背包问题，解空间是：{0，0，0}，{0，0，1}，{0，1，0}，{0，1，1}，{1，0，0}，{1，0，1}，{1，1，0}，{1，1，1}该问题有23个可能解。回溯法—01背包01背包问题的解空间树为子集树，解空间树的深度为问题的规模n。回溯法—01背包（3）搜索解空间背包问题的解空间包含2n种可能解，存在某种或某些物品无法装入背包的情况，因此需要设置约束条件，判断装入背包的物品总重量是否超出容量。约束函数为cw+w[i]≤m，cw表示当前装入背包的物品重量，w[i]为第i个物品的重量，m为背包容量。回溯法—01背包限界函数为cp+brp>bestp，其中，cp表示当前装入背包的物品价值，brp表示剩余容量可容纳的剩余物品的最大价值，bestp表示当前最优值。回溯法—01背包回溯法—01背包算法实现回溯法—01背包回溯法—01背包算法分析时间复杂度：

时

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论