基于集合求解01背包问题的跳跃点法

详细信息    查看全文 | 推荐本文 |

	作者：王金燕 关键词：01背包 ; 动态规划 ; 跳跃点 ; set集合 中文刊名：DZRU 英文刊名：Electronic Technology & Software Engineering 机构：山东科技大学; 出版日期：2019-05-10 14:04 出版单位：电子技术与软件工程 年：2019 期：No.155 语种：中文; 页：DZRU201909123 页数：1 CN：09 ISSN：10-1108/TP 分类号：164

摘要

01背包问题的名称来源于不可切分物品的最优装包策略。由于其NP完全性,很难采用一般的算法进行求解。本文在传统的动态规划求解策略基础上,分析其面对大规模问题的局限性,采用改进的跳跃点法对问题做出求解,并通过STL模板库set存储求解过程中的跳跃点集,以降低问题的时间空间复杂度。
        

引文

[1]王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2012.
    [2]动态规划-百度文库《互联网文档资源》(http://wenku.baidu.c),2012.