




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
背包问题例1(背包问题)设有一辆背包可以装入的物品情况如下表:问:如何安排装入方案,使背包一次装入的货物总价值最大?解:设xi为背包装入第i种货物的件数。货物(件)12…n
最大装入量
单位重量w1
w2…wn
a单位价值c1
c2…cn注:若每种物品的最大件数为1,则xi取值为0或1,称为0-1背包问题阶段:按照物品的种类将装入背包的过程分为n个阶段,每个阶段装入一种物品;状态变量sk:装前k-1种的物品的可用背包容量;决策变量xk
:装入第k种物品的数量;状态转移方程:sk=sk+1-wkxk最优指标函数fk(sk+1):若只装入k种物品,背包容量为sk+1时装入物品的最大价值动态规划的顺序递推方程(顺序解法)显然,我们要求的是fn(a)例1:有一艘货船的最大载重量为5吨,用以装载三种货物,每种货物的单位重量及单价如表所示。应如何装载使总重量最大?货物(件)123
最大装入量
单位重量3255单位价值8512解:按顺序装入三种货物,装入过程分为三个阶段,k=1,2,3。采用动态规划的顺序解法求解。当k=2时当k=1时当k=3时由所以所装入的最大物品总价值为13。
旅行商(TSP)问题设有一个由n个城市构成的交通网络,各个城市之间的路径长度已知。一个推销员从城市1出发到其他城市,每个城市必须经过且只经过一次然后返回城市1。问:该推销员该如何选择行走路线使得总的路程最短。记所有城市的集合为V={v1,v2,…,vn};
城市i到城市j的距离为dij;递推公式(动态规划的基本方程):很显然,我们最后需要求的是,其中将推销员的旅行过程分为n个阶段;第k阶段的状态为:(所在的城市vi,所经过的城市集合Vk
)最优值函数fk(vi,Vk):从城市1出发,经过k个城市(经过城市集合为Vk)到达城市vi
的最短路径长度采用顺序解法进行求解例2:求解4个城市的旅行商问题,其4个城市之间的距离如矩阵所示。求推销员从城市1出发经过所有城市一次并回到城市1的最短路径及路径长度。解:由边界条件可知k=1:从v1出发,经过一个城
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 海洋油气管道完整性管理考核试卷
- 油气仓储环节的智能化发展路径探索与研究考核试卷
- 热电联产在渔业养殖的实践考核试卷
- 摩托车发动机气门座材料与耐磨性考核试卷
- 充电设施在公共交通领域的应用考核试卷
- 玉米淀粉在植物组织培养中的培养基优化与生长促进考核试卷
- 化工设备密封系统设计与应用考核试卷
- 石油开采业的经济影响考核试卷
- 玻璃制品环境适应性考核试卷
- 游艺用品的供应链优化与物流管理考核试卷
- 【企管】年屠宰4200万只肉鸭技术工艺改造项目可行性报告
- 8.6《林黛玉进贾府》课本剧剧本
- mt696-1997煤矿用高倍数泡沫灭火装置通用技术条件
- GB/T 11693-2022船用法兰焊接座板
- JJG 388-2001纯音听力计
- GB/T 18926-2008包装容器木构件
- GB/T 16422.1-2019塑料实验室光源暴露试验方法第1部分:总则
- 乳品质量安全监督管理条例及配套规章解读(PPT)
- 2.6《古代生物的多样性》教学课件
- 口才技巧之一交谈技巧课件
- 初中美术-手工书设计教学课件设计
评论
0/150
提交评论