算法设计与分析 课件 第六章 回溯法6.3.1 饲料投喂问题_第1页
已阅读1页，还剩7页未读， 继续免费阅读

付费下载

下载本文档

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

文档简介

计算机算法设计与分析第6章回溯法6.3.1饲料投喂问题饲料投喂问题：某农场有n头奶牛，假设每头奶牛仅有投喂或不投喂饲料两种选择，奶牛i需要投喂wi千克饲料才能产出vi千克牛奶。农场现有饲料总量为C千克，问如何投喂才能使得奶牛产奶量最大化？6.3.1饲料投喂问题农场奶牛饲料投喂问题是一个典型的0-1背包问题，假设农场有n=4头奶牛，农场饲料总量C为10千克，每头奶牛需要的饲料量和能够产出的牛奶量如下，w_i投喂饲料重量，v_i投喂后的产量。牛奶编号w_iv_i12523835144521问题的解向量空间奶牛投喂的解向量空间可以表示为一个四元组X=(x1,x2,x3,x4)，xi的值表示第i头奶牛投喂情况。由于每头奶牛仅有投喂或不投喂饲料两种选择，所以xi(i=1,2,3,4,表示奶牛编号)只能取值为0或1，xi=0表示不投喂，xi=1表示进行投喂。解空间树用回溯法求解，需要生成一棵二叉树（子集树）来表示问题的解空间。x4=1,2+3+5+5>10不可行，回溯

ABx4=0x4=1,5+5≤10x3=1,5<10x2=0,C=10x1=0,C=10初始状态，饲料总量C=10x1=1,2<10x2=1,2+3<10x3=1,2+3+5≤10编号w_iv_i12523835144521数学建模C语言实现voidbacktrack(inti,intcw,intcv){ if(i==n){ if(cv>bestv&&cw<=C){

bestv=cv; for(intk=0;k<n;k++)bestx[k]=x[k];

} return; } x[i]=1; backtrack(i+1,cw+w[i],cv+v[i]); x[i]=0; backtrack(i+1,cw,cv);}bestv记录下前最优值x[i]=1,递归到下一层x[i]=0,递归到下一层bestx记录当前最优解效率分析深度优先搜索回溯法求解饲料投喂问题（0-1背包问题）的时间复杂度分析，由问题解空间树可知，n头奶牛投喂过程产生的解空间树，其结点总数为：1+2+22+...+2n=2n+1-1≤2*2n=O(2n)。效率是比较低的，时间复杂度O(2n)是一个指数数量级。若要提高

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

温馨提示

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

最新文档

评论

0/150

提交评论