文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 基于MATLAB的0—1背包问题的动态规划方法求解 DP算法 分治法 递归法 NP难题
侵权投诉

基于MATLAB的0—1背包问题的动态规划方法求解 DP算法 分治法 递归法 NP难题

0-1背包的规划问题

维普资讯 doc.guandang.net

第

年 20 06

期 4月

计算机技术与发展 ( M P r{’、I 1) U f】 F NO1 I E(』X; ANI ) Y )IFV【 PM ENq』)、

VO . 6 NO 4 11 . Ap .2 0 r 06

基于 Mal t b的 0—1包问题的动态规划方法求解 a背 王乐,王世卿,张静乐 (郑州大学信息工程学院,河南郑州 4 0 5 ) 50 2 摘要:包问题是经熊的 N背 P~hr组合优化问题之一,经济管理、分配、 a d在资源投资决策、载设计等领域有着重要的应装

用价值。文中用动态规划方法解决 0背包问题,在 Maa6 5境下对其算法进行测试和与其他方法对比分析,~l通过 tb.环 l表

明应用该方法可节省大量的计算时间,因而具有更高运行效率。 关键词: 1 O背包问题; P法;治法; D算分递归法; P难问题; rb N Mal a中图分类号: P 0 . T 3 16文献标识码: A文章编号:0 5 7 120 )4 0 8-2 10—35 (0 60—08 - O

DP Al o ih fS l i g 0— 1’ a s c o e s d o a l b g rtm o ovn S Kn p a k Pr blm Ba e n M ta W A e WA NG L, NG h-ig H S i n,Z ANG J gl q i - n e ( ol e f no C lg fmmt nE gneig Z eghuUn e i,h nzo 5 0 2 C i ) e ol i n ier,hn zo i r t Z egh u4 0 5, hn o n v sy a Ab ta tTh n p k p o lm saca scNP— h r r be i h o bn t n lo tmiain. ti v la l nm a yfed u ha e sr c: ek a ̄c rbe i lsi adp o lm nt ecm iai a p i zt o o I s au bei n ilss c sr— su c si me tiv sme td cso n o dn e in. i p p r ̄ le h o re as gn n,n et n,e iina dla igd sg Ths a e v dte0— 1k a sc r be b n p ak po lm yDPag rtm,n etteer lo ih a dts h l l g rt

alb,, eag rtm h wsiss p ro i fe o aigwiho h rmeh d . o ih i M ta 6 5 Th loih so t u eirt a tre mp rn t t e to s m n y

Ke o d: yw r s O—l n p kp b m; lo i m; ii n n d—c n u r g rc ri l r h; k ̄c r l DP a r h dv ig—a a o e g t d o q ei;eu s ea o i m NP—h r r be n v g t a d po l m;Mal tb a

0引言 背包问题是一个典型的 N P—hr问题, ad求解背包问题有着广泛的应用前景,在学术上,可以解决 0整数规—1

值总和最大的问题。如果所有物品的重量之和小于背包的容量,则问题极其简单,所得利益也就是所有物品的价值之和,而实际问题往往是背包的容量小于物品的重量之和‘用形式化方法可对该问题描述为: 2。 2 J 设为背包的容量,n个物品的重量组成一向量

划问题或某类可归纳为 0背包问题的子问题;一l在实际应用中,对于解决资源分配、投资决策、预算控制、目选项 择和货物装运等问题,其规划方法优劣将直接影响到运作

(,, w )其价值组成另一向量 (,, )删lw2…, , I…,, 2 > 0训>0 V>0 1,,i (≤≤ n。 )要找出另一 n元向 量 (, 2…, ) a∈{,} 1 lz, ,T, 0 1,≤≤ n 1 ,表示选,表 O 示不选该物品。

效率与成本…。因此,对该问题的研究倍受人们关注。文中在对多种不同的求解方法如贪婪算法、回溯法、分枝一 界限法等进行分析研究的基础上,采用动态规划算法解决此类问题。通过在 Mal 6 5 t b .环境下对其算法进行测试, a

并与其他解决背包问题的方法进行分析对比,表明动态规划方法以空间换时问,对一个问题或多次出现的相同问题仅需解决一次,因此可节省大量的计算时间而具有更高运 行效率的优越性。

由此,一l 0背包问题要求:a∑, Mx且满足以下 l

两个约束条件: —

() 1 l

wi W o≤ c 1≤≤/,/

( )童∈{, j 2 01

l问题描述 背包问题是一个典型的 N P难问题,它的数学模型实际上是一个 0规划问题。0 l一l 背包问题是指有

不同

也就是说对 0— 1包问题,以通过求出变量 .,背可 2 7 I

。…,的一个决策序列来得到它的解,, 而对变量的决策就是决定它足取 0值还是取 l。值

价值、不同重量的物品件,求从这件物品中选取一部 分物品且对每一物品,么选,要要么不选,被选物品的满足

2采用的动态规划方法 对解决复杂问题虽然不能简单地把它分解成几个子 问题,但可以分解出一系列的相关子问题。因简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的

总重量不超过背包指定的限制重量且达到被选物品的价 收稿日期:0 5—0【 20 7 ) 9

作者简介:王

乐 (9 1, . 18一)女河北安新人,硕士研究生,研究方向

解的方法,问题求解耗时会按问题规模呈幂级数增加。为 节约重复求相同子问题的时间,文中引入一个动态变化的数组,不管每一次对子问题求得的解是否对最终解有用,

为决策支持与企业信息化;壬世卿,硕士研究生导师,究方向为电研 子商务、数据挖掘。

基于MATLAB的0—1背包问题的动态规划方法求解 DP算法 分治法 递归法 NP难题

第1页

你可能喜欢

  • matlab动态规划
  • 背包问题
  • 动态问题
  • 动态规划问题
  • 蚁群算法
  • 背包算法
  • 装箱问题
  • MATLAB线性规划

热门文档

相关文档

  • 基于Matlab的0_1背包问题的动态规划方法求解

    2006 基于 Matlab 的 0- 1 背包问题的动态规划方法求解王 乐, 王世卿, 张...关键词: 0- 1 背包问题; DP 算法; 分治法; 递归法; NP 难问题; Matlab ...

  • 【论文】基于动态规划法求解动态0-1背包问题

    在动态规划法基础上,提出了一种求解背包载重随机变化的RTVKP问题的确定性算法,分析了其复杂度和成功求解需要满足的条件。对两个大规模实例的计算表明,该算法是求解...

  • 实验3. 基于动态规划方法求解0-1背包问题

    算法 描述、算法正确性证明、算法分析、算法实现与测试) ,在针对 0-1 背包问题求解的实践中 理解动态规划 (Dynamic Programming, DP) 方法的思想、求解策略及步骤...

  • 解0-1背包问题的动态规划算法

    2、求解问题的动态规划原理与算法 2.1动态规划原理的描述 求解问题的动态规划有向前处理法向后处理法两种,这里使用向前处理法求解 0/1背包问题。对于0/1背包问题...

  • 求解0-1背包问题算法综述

    2 2.1 求解 0-1 背包问题的常用算法动态规划法 ...是美国 0-1 背包问题是一个 NP 难题, 它在很多...本 文利用 MATLAB 软件中的 SORTROWS 函数进行排序 ...

  • 动态规划0—1背包问题

    动态规划0—1背包问题_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 动态规划0—1背包问题_计算机软件及应用_IT/计算机_专业资料。 ...

  • 动态规划(dp算法)

    递归策略 在例 3 - 4 中已建立了背包问题的动态规划递归方程,求解递归式( 1 5 - 2)的一个很自然 的方法便是使用程序 1 5 - 1 中的递归算法。该模块...

  • 基于贪心策略的遗传算法求解0-1背包问题

    针对 0-1 背包问题的解法种类繁多,如贪心算法、动态规划、遗传算法等等。本 ...matlab 根据邻接矩阵作图... 4页 免费 遗传算法及其应用实例 20页 1下载券 第...

  • 动态规划-0-1背包

    递归定义最优值由前面的最优值过程分析实例,根据0-1背包问题的最 优子结构...思想动态规划算法与分治法类似,其基本思想也 是将待求解问题分解成若干个子问题...

  • 关于0_1背包问题的算法研究

    1 背包问题的算法研究李北斗 (中国地质大学信息工程学院 武汉 430074) 摘 0 /...但是动态规划算法有着自身的特点 , 解决了分治法中相同子问题重复求解的问题 。...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email