子集和问题的改进算法

An Improved Algorithm for the Subset Sum Problem

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

Due to the importance of the subset sum problem in cryptosystem,in the past two decade,much effort has been done in order to find techniques that could lead to practical algorithms with reasonable running time- Based on the two-list four-table algorithm,this paper proposes an improved algorithm for the solution of subset sum problem. To find a solution for the n-element subset problem,the proposed algorithm needs O(2^(n/2-ε)) memory, 1≤ε≤εn/4,and in O(ε(2^(n/2)) time. The theoretic analysis and the computational experiments show that our proposed algorithm can solve the subset problem instances that can't be solved before,thus it is an improved result over the past researches.