背包问题的动态规划改进算法

发布时间：2017-09-20 18:03

  本文关键词：背包问题的动态规划改进算法

  更多相关文章： 背包问题 动态规划 状态表示 决策依赖

【摘要】：在动态规划算法的基础上提出了改进算法,对于0-1背包问题,改进了动态规划算法的状态表示以减少需要计算的状态个数来求解该问题;对于完全背包问题,简化了动态规划算法状态的决策依赖关系来求解该问题.实验结果表明:所提出的改进算法在时空效率上具有一定的有效性和优越性.
【作者单位】： 中南民族大学计算机科学学院;
【关键词】： 背包问题 动态规划 状态表示 决策依赖
【基金】：国家自然科学基金资助项目(71003038)
【分类号】：TP301.6
【正文快照】： 背包问题在现实生活中广泛地应用于需要基于有限资源进行选择判断的领域[1],如货物装载、投资组合、下料问题等[2],因此对该问题的研究具有重要的实际意义.背包问题可以衍生出0-1背包问题、完全背包问题和多重背包问题等[3].解决0-1背包问题的动态规划算法的时空复杂度为O(n W

【相似文献】

中国期刊全文数据库 前10条

1 何文明,朱起定;背包问题的循环及并行解[J];湘潭师范学院学报(社会科学版);2000年03期

2 任瑞征,严蔚敏;整数背包问题的应用及其算法研究[J];小型微型计算机系统;2001年02期

3 叶俊,刘贤德,韩露;基于博弈论的背包问题优化算法[J];华中科技大学学报(自然科学版);2003年09期

4 罗小虎,赵雷;一个解决0/1背包问题的蚁群方法[J];苏州大学学报(工科版);2004年01期

5 宋翔,聂义勇,储诚斌;无限制背包问题的爬山算法[J];小型微型计算机系统;2004年07期

6 谢涛,陈火旺,康立山;二次背包问题的一种快速解法[J];计算机学报;2004年09期

7 王喜凤;浅析0/1背包问题[J];电脑知识与技术;2004年29期

8 华中生,张斌;求解可分离连续凸二次背包问题的直接算法[J];系统工程与电子技术;2005年02期

9 宋海洲;魏旭真;;求解0-1背包问题的混合遗传算法[J];华侨大学学报(自然科学版);2006年01期

10 熊伟清;魏平;王小权;;蚁群算法求解多维0/1背包问题[J];计算机工程与科学;2006年10期

中国重要会议论文全文数据库 前6条

1 乔善平;朱波;赵玲;;基于移动Agent的0-1背包问题分布式求解[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

2 高尚;;背包问题的分布估计算法[A];2013年中国智能自动化学术会议论文集（第五分册）[C];2013年

3 徐俊杰;忻展红;;粒子群优化在0/1背包问题中的应用[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

4 姜宇;苏中滨;郑萍;;求解O/1背包问题的算法综述[A];黑龙江省计算机学会2009年学术交流年会论文集[C];2010年

5 刘裴寰;姜青山;王备战;史亮;;基于K均值聚类求解多维背包问题的算法[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

6 李伟;吕克伟;;类背包DH问题的比特安全性研究[A];第28次全国计算机安全学术交流会论文集[C];2013年

中国博士学位论文全文数据库 前2条

1 黄斌超;限制性多重背包问题的研究[D];云南大学;2015年

2 TRUONG KHAC TUNG;[D];湖南大学;2013年

中国硕士学位论文全文数据库 前10条

1 史如意;带流量约束的星型图背包问题[D];浙江大学;2015年

2 孙飞;改进萤火虫算法求解0-1背包问题[D];西北师范大学;2015年

3 聂大干;森林优化算法的改进及离散化研究[D];兰州大学;2016年

4 潘夏福;混合蚁群算法求解0-1背包问题[D];厦门大学;2008年

5 朱阅岸;解0-1背包问题的算法比较和改进[D];暨南大学;2011年

6 史今驰;背包问题的实用求解算法研究[D];山东大学;2005年

7 郑杨凡;基于属性论的0-1背包问题算法研究[D];上海海事大学;2005年

8 李其;有偿在线背包问题的研究[D];大连理工大学;2012年

9 孟晓笑;并行环境下0-1背包问题的解决策略[D];湖北大学;2011年

10 钟海林;背包问题的一种新算法：降维递归算法[D];江西师范大学;2008年

，

本文编号：889559