文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 基于Matlab的0_1背包问题的动态规划方法求解
侵权投诉

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

第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 采用的动态规划方法

对解决复杂问题虽然不能简单地把它分解成几个子问题,但可以分解出一系列的相关子问题。因简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。为节约重复求相同子问题的时间,文中引入一个动态变化的,,

第1页

你可能喜欢

热门文档

相关文档

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