| 引用本文: | 姜新文,彭立宏.子集和问题的分治求解.[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[点击复制] |
|
| |
|
|
| 本文已被：浏览 6566次 下载 5937次 |
| 子集和问题的分治求解 |
| 姜新文, 彭立宏 |
|
(国防科技大学 计算机学院，湖南 长沙 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 |
|
|
