0/1背包问题及其解法研究

被引：3

作者：

黄波

蔡之华

机构：

[1] 中国地质大学计算机学院

[2] 中国地质大学计算机学院湖北武汉430074

来源：

电脑知识与技术 | 2007年 / 07期

关键词：

0/1背包问题; 贪心方法; 动态规划; 回溯法; 分枝-限界法; 遗传算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

0/1背包问题是实际当中经常遇到的一类经典NP-hard组合优化问题之一。本文分别从贪心方法、动态规划、回溯法、分枝-限界法,遗传算法这五种算法设计方法入手,概述了各种设计方法的基本原理,提出了求解0/1背包问题的算法思想,并对算法进行分析,提出了改进方法。

引用

页码：229 / 231

页数：3

共 8 条

[1] 基于遗传算法的0/1背包问题求解 [J].

王莉 ;

绍定宏 ;

陆金桂 .

计算机仿真, 2006, (03) :154-156

[2] 0/1背包问题 [J].

陈莹 ;

廖利 .

电脑知识与技术, 2006, (05) :96-97

[3] 0-1背包问题的两种扩展形式及其解法 [J].

刘玉娟 ;

王相海 .

计算机应用研究, 2006, (01) :28-30

[4] 对背包问题的计算机算法研究 [J].

闫建红 .

电脑开发与应用, 2005, (08) :63-63

[5] 背包问题的一种自适应算法 [J].

李肯立 ;

李庆华 ;

戴光明 ;

周炎涛 .

计算机研究与发展, 2004, (07) :1292-1297

[6] 求解背包问题的新型算法 [J].

于秀霞 .

长春大学学报, 2002, (02) :3-5

[7] 基于遗传算法的0/1背包问题求解 [J].

霍红卫，许进，保铮 .

西安电子科技大学学报, 1999, (04) :101-105

[8] 0－1背包问题的多重分枝－限界算法 [J].

李鸣山，郑海虹 .

武汉测绘科技大学学报, 1995, (01) :83-87

← 1 →