计算机工程 ›› 2008, Vol. 34 ›› Issue (4): 7-9.doi: 10.3969/j.issn.1000-3428.2008.04.003

• 博士论文 • 上一篇    下一篇

一种求解背包问题的自适应算法

江 华1,2,谭新星2,李 祥1   

  1. (1. 贵州大学计算机理论与软件研究所,贵阳 550025;2. 广东韶关学院计算机系,韶关 512005)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-02-20 发布日期:2008-02-20

Adaptive Algorithm for Solving Knapsack Problem

JIANG Hua1,2, TAN Xin-xing2 , LI Xiang1   

  1. (1. Institute of Computer Theory and Software, Guizhou University, Guiyang 550025; 2. Department of Computer, Guangzhou Shaoguan University, Shaoguan 512005)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-02-20 Published:2008-02-20

摘要: 针对二表算法和动态二表算法求解背包问题,提出一个并行自适应算法,能用 个处理机、 的时间、 的空间求解背包问题 ,根据处理机的数目以及存储器的容量来选择参数,充分利用已有的硬件资源,以求得最快的求解速度。实验结果证明了该算法的有效性。

关键词: 背包问题, NP问题, 并行算法, 时间-存储器-处理机折中

Abstract: Based on the two-list algorithm and the two-list four-table algorithm, this paper proposes parallel adaptive algorithm for solving the knapsack problem. It uses processors, time, and memory to solve the knapsack problem , whose parameter can be selected by numbers of processors and amounts of memory that can make full use of the existing hardware resources to find the fastest solution. Experimental results show that the algorithm is effective.

Key words: knapsack problem, NP problem, parallel algorithm, time-memory-processor tradeoff

中图分类号: