子集和问题的改进算法

摘要：

@@ 1.导言
子集和问题可描述如下:给定n个正整数W=(w1,w2,…,wm)和正整数M,要求寻找这样一个子集I {1,2,…,n},使得∑wi=M,i∈I.子集和问题属于NP完全问题[2],直接的枚举搜索可能遍历问题的所有2n个解空间,即直接搜索最坏情况下的时间复杂性为O(2n).

机标关键词：子集和问题、改进算法、Subset Sum、正整数、时间复杂性、最坏情况、直接搜索、完全问题、解空间、描述、导言

所属期刊栏目：30

分类号：O1(数学)

资助基金：国家自然科学基金60273075;国家高技术研究发展计划863计划863-306 ZD-11-01-06

在线出版日期：2004-01-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：16-17,76