第16卷 第4期 2006年4月
计算机技术与发展
COMPUTERTECHNOLOGYANDDEVELOPMENT
l.16 No.4 VoApr.2006
基于Matlab的0-1背包问题的动态规划方法求解
王 乐,王世卿,张静乐
(郑州大学信息工程学院,河南郑州450052)
摘 要:背包问题是经典的NP-hard组合优化问题之一,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。文中用动态规划方法解决0-1背包问题,通过在Matlab6.5环境下对其算法进行测试和与其他方法对比分析,表明应用该方法可节省大量的计算时间,因而具有更高运行效率。关键词:0-1背包问题;DP算法;分治法;递归法;NP难问题;Matlab
中图分类号:TP301.6 文献标识码:A 文章编号:1005-3751(2006)04-0088-02
DPAlgorithmofSolving0-1 sKnapsackProblemBasedonMatlab
WANGLe,WANGShi qing,ZHANGJing le
(CollegeofInformationEngineering,ZhengzhouUniversity,Zhengzhou450052,China)
Abstract:TheknapsackproblemisaclassicNP-hardprobleminthecombinationaloptimization.Itisvaluableinmanyfieldssuchasre sourceassignment,investment,decisionandloadingdesign.Thispapersolvedthe0-1knapsackproblembyDPalgorithm,andtesttheal gorithminMatlab6.5.Thealgorithmshowsitssuperiorityaftercomparingwithothermethods.
Keywords:0-1knapsackproblem;DPalgorithm;dividing-and-conquering;recursivealgorithm;NP-hardproblem;Matlab
0 引 言
背包问题是一个典型的NP-hard问题,求解背包问题有着广泛的应用前景,在学术上,可以解决0-1整数规划问题或某类可归纳为0-1背包问题的子问题;在实际
应用中,对于解决资源分配、投资决策、预算控制、项目选择和货物装运等问题,其规划方法优劣将直接影响到运作效率与成本。因此,对该问题的研究倍受人们关注。文中在对多种不同的求解方法如贪婪算法、回溯法、分枝-界限法等进行分析研究的基础上,采用动态规划算法解决此类问题。通过在Matlab6.5环境下对其算法进行测试,并与其他解决背包问题的方法进行分析对比,表明动态规划方法以空间换时间,对一个问题或多次出现的相同问题仅需解决一次,因此可节省大量的计算时间而具有更高运行效率的优越性。
[1]
值总和最大的问题。如果所有物品的重量之和小于背包的容量,则问题极其简单,所得利益也就是所有物品的价值之和,而实际问题往往是背包的容量小于物品的重量之和[2]。用形式化方法可对该问题描述为:
设W为背包的容量,n个物品的重量组成一向量(w1,w2, ,wn),其价值组成另一向量(v1,v2, ,vn),W>0,wi>0,vi>0(1!i!n)。要找出另一n元向量(x1,x2, ,xn),xi {0,1},1!i!n,1表示选,0表示不选该物品。
由此,0-1背包问题要求:Max两个约束条件:
(1)
i=1n
i=1
#vixi,且满足以下
n
#wixi
!W
(2)xi {0,1} 1!i!n
也就是说对0-1背包问题,可以通过求出变量x1,x2, ,xn的一个决策序列来得到它的解,而对变量xi的决策就是决定它是取0值还是取1值。
1 问题描述
背包问题是一个典型的NP难问题,它的数学模型实际上是一个0-1规划问题。0-1背包问题是指有不同
价值、不同重量的物品n件,求从这n件物品中选取一部分物品且对每一物品,要么选,要么不选,满足被选物品的总重量不超过背包指定的限制重量且达到被选物品的价
收稿日期:2005-07-09
作者简介:王 乐(1981-),女,河北安新人,硕士研究生,研究方向为决策支持与企业信息化;王世卿,硕士研究生导师,研究方向为电子商务、数据挖掘。
2 采用的动态规划方法
对解决复杂问题虽然不能简单地把它分解成几个子问题,但可以分解出一系列的相关子问题。因简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。为节约重复求相同子问题的时间,文中引入一个动态变化的,,
2006 COMPU TER TECHNOLO GY AND DEV ELOPM EN T 基于 Matlab 的 0 - 1 背包问题的动态规划方法求解王 ,王世卿 ,张静乐 乐 ( 郑州大学 信息工程学院 ,...
基于Malt b的0—1包 问题 的动态 规划方 法求解 a背王 乐, 王世 卿, 张静 乐 ( 郑州大学 信息工程学院, 河南 郑州 405)502 摘要: 包问题 是 经熊 ...
动态规划0或1背包问题 8页 10财富值 基于Matlab的0_1背包问题的... 3页 ...[1 - 2] 法求解问题 ,首先要把实际问题抽象成数学模型 , 再进行相应的算法...
第3 9卷第 7期 210 2年 7月 计 算 机 科 学 Vo.9No713 . Coue Sinemptrcec Jl 02uy21 基于动态规划法求解动态01包 问题 —背贺 毅朝 田海燕 张新禄...
基于MATLAB的0—1背包问题... 3页 5财富值 基于Matlab的动态规划程序... ... 动态规划求解方法的Matlab实现及应用[1].txt爱情是艺术,结婚是技术,离婚是算术...
基于Matlab的0_1背包问题... 3页 1下载券喜欢此文档的还喜欢...一个会获得问题最优解的决策序列, 运用动态规划方 法的前提是所求解问题的最...
3页 1下载券 基于MATLAB的0—1背包问... 3页 2下载券喜欢此文档的还喜欢... 文章对动态规划问题的求解方法进行了分析研究 , 根据问题的特点 、 难点和关键...
第2 卷第1期92012年3月 经 济 数 学JOURLO NA FQUANITV CTTAIEEONOMCIS Vl2,o1o.9N.Mr2012a. 一种求解分组 0-1 背包问题的动态规划法蒋亚军1,易学军2 *...
实验3. 基于动态规划方法求解 0-1 背包问题 实验内容本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法 描述、算法正确性证明、算法分析...
决策过程 ,应用动态规划方法并且在计算机上通过MATLAB编程方便地求解资源分配问题.... 动态规划选址,背包matla... 2页 免费 动态规划求解方法的Matl... 26页 ...
热门文档