引用本文: | 姜新文,彭立宏.子集和问题的分治求解[J].国防科技大学学报,2004,26(6):103-106.[点击复制] |
JIANG Xinwen,PENG Lihong.A New Algorithm for Subset Sum Problem with Time Complexity[J].Journal of National University of Defense Technology,2004,26(6):103-106[点击复制] |
|
|
|
本文已被:浏览 6126次 下载 5458次 |
子集和问题的分治求解 |
姜新文, 彭立宏 |
(国防科技大学 计算机学院,湖南 长沙 410073)
|
摘要: |
介绍了求解子集和问题的一个分治算法。设给定的n个正整数为A(1),A(2),…,A(n-1),A(n),给定的子集和为正整数M,算法的时间复杂性为O(nlog2(M+1)+1),空间复杂性为O(n)。当M较小时,算法复杂性优于二表算法的复杂性。 |
关键词: 子集和问题 NP完全问题 分治策略 算法 |
DOI: |
投稿日期:2004-03-05 |
基金项目: |
|
A New Algorithm for Subset Sum Problem with Time Complexity |
JIANG Xinwen, PENG Lihong |
(College of Computer, National Univ. of Defense Technology, Changsha 410073,China)
|
Abstract: |
We introduce a new algorithm for subset sum problem. For any given problem with A(1),A(2),…,A(n-1),A(n),and M, the time complexity of the algorithm is O(nlog2(M+1)+1)and the space complexity is O(n), where A(1),A(2),…,A(n-1),A(n),and M are all positive integers. This result is better than that of the two-list algorithm when M is relatively small. |
Keywords: subset sum problem NP complete problem divide and conquer algorithm |
|
|