| 子集和问题的分治求解 |
| |
| 引用本文： | 姜新文,彭立宏.子集和问题的分治求解[J].国防科技大学学报,2004,26(6):103-106. |
| |
| 作者姓名： | 姜新文 彭立宏 |
| |
| 作者单位： | 国防科技大学计算机学院,湖南,长沙,410073;国防科技大学计算机学院,湖南,长沙,410073 |
| |
| 摘 要： | 介绍了求解子集和问题的一个分治算法。设给定的n个正整数为A(1),A(2),…,A(n-1),A(n),给定的子集和为正整数M,算法的时间复杂性为O(nlog2(M+1)+1),空间复杂性为O(n)。当M较小时,算法复杂性优于二表算法的复杂性。
|
| 关 键 词： | 子集和问题 NP完全问题 分治策略 算法 |
| 文章编号： | 1001-2486(2004)06-0103-04 |
| 收稿时间： | 3/5/2004 12:00:00 AM |
| 修稿时间： | 2004年3月5日 |
A New Algorithm for Subset Sum Problem with Time Complexity |
| |
| JIANG Xinwen and 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. |
| |
| Authors: | JIANG Xinwen and PENG Lihong |
| |
| Abstract: | |
| |
| Keywords: | subset sum problem NP complete problem divide and conquer algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《国防科技大学学报》浏览原始摘要信息 |
| 点击此处可从《国防科技大学学报》下载免费的PDF全文 |
|
