An 0(1.414n) volume molecular solution for the 0–1 knapsack problem on DNA-based supercomputing

Being a typical NP-complete problem, 0-1 knapsack problem is one of the classical combinatorial optimization problems, the traditional parallel processing techniques can not break through the limitations of the number of processors or the time´s exponential increasing. But DNA computing is one of the potential strategies for solving these combinatorial optimization problems availably. In [8], Majid et al solved the problem with exponential O(2^q) DNA chains. In this paper, the objective is to solve the 0-1 knapsack problem with as few DNA chains as possible, for that we apply the divide-and-conquer to the DNA algorithm, and propose the new DNA computer algorithm for solving the 0-1 knapsack problem. This algorithm decreases the number of DNA chains from O(2^q) to sub-exponential O(2^q/2). In other words, it can theoretically extend the number of dimension from 60 to 120 when using the DNA computing for solving the 0-1 knapsack problem.