Application of Integer Division with Remainder in Subset Sum Problem
Qiu Wei-xing · Jisuanji gongcheng · 2011
This paper presents a quick algorithm for the subset sum problem by using principles of integer division with a remainder and birthday problem.The algorithm description is given.Next,its termination in finite steps,as well as its output correctness in its solvable space is theoretically proved,and its success rate is analyzed.In the end,by random experiments,it makes a comparison of time and success rate with an approximation counterpart.Experimental results show that this approach has lower time complexity than the approximation algorithm and has a very high probability of success for problem samples of large sets.