




A Genetic Algorithm to Solve the Subset Sum Problem based on Parallel Computing 

PP: 921925 

Author(s) 

Lei Li,
Kai Zhao,
Zuwen Ji,


Abstract 

The subset sum problem is to find subsets in a given number set, meanwhile number sum of the subset is equal to appointed
value. It is a classical NPcomplete problem in graph theory. It can be solved by the electronic computer in exponential time. In this
paper, we consider a DNA procedure for solving the subset sum problem in the AdlemanLipton model. The procedure works in O(n)
steps for the subset sum problem of an undirected graph with n vertices. The innovation of the procedure is the ingenious choice of the
vertices strands’ length, which can get the solution of the problem in proper length range and simultaneity simplify the complexity of
the computation. 




