%0 Journal Article
%T An Improved Algorithm for the Subset Sum Problem<br>子集和问题的改进算法
%A LI Ken-Li LI Qing-Hua ZHANG Hong-Jun
%A <br>李肯立
%A 李庆华
%A 张红君
%J 计算机科学
%D 2003
%I 
%X Due to the importance of the subset sum problem in cryptosystem,in the past two decade,much ellort 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-g) 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.
%K Subset sum problem
%K NP-complete
%K Two-list four-table algorithm
%K Merkle-Helman cryptosystem<br>子集和
%K 改进算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=9C4F616870887A84&yid=D43C4A19B2EE3C0A&vid=340AC2BF8E7AB4FD&iid=708DD6B15D2464E8&sid=7801E6FC5AE9020C&eid=BCA2697F357F2001&journal_id=1002-137X&journal_name=计算机科学&referenced_num=3&reference_num=10