南京邮电大学学报（自然科学版）2012，Vol.32Issue(6)：92-95,4.
求解子集和问题的快速算法
A Quick Algorithm for the Subset Sum Problem
王蔚 1邱伟星1
作者信息
- 1. 南京邮电大学计算机学院,江苏南京210023
- 折叠
摘要
Abstract
In this paper we present a quick algorithm for the subset sum problem by using principles of integer division with a remainder and birthday problem. We theoretically prove that the algorithm has a time 1-(T-2/T-1)n2m . Experimental results show that our approach
has much lower time consumption than the traditional exponential-time algorithm and has a very high success rate for the problem samples of large sets.关键词
子集和问题/背包问题/整数除法/生日问题Key words
subset sum problem/knapsack problem/integer division/birthday problem分类
信息技术与安全科学引用本文复制引用
王蔚,邱伟星..求解子集和问题的快速算法[J].南京邮电大学学报（自然科学版）,2012,32(6):92-95,4.
