Affiliations: [a] State Key Laboratory of Simulation and Regulation of River Basin Water Cycle, China Institute of Water Resources and Hydropower Research, Beijing, P.R. China | [b] College of Information, Shanghai Ocean University, Shanghai, P.R. China | [c] School of Information and Engineering, Wenzhou Medical University, Wenzhou, P.R. China | [d] College of Mathematics and Information Science, Guiyang University, Guizhou, P.R. China
Correspondence:
[*]
Corresponding author. Tunhua Wu, School of Information and Engineering, Wenzhou Medical University, Wenzhou 325035, P.R. China. E-mail: [email protected].
Abstract: The 0-1 knapsack problem is one of the classical NP-hard problems and has been one of the hot research topics in the last few decades. It offers many practical applications in optimization and applied mathematics, such as project selection, resource distribution, investment decision-making and so on. Simultaneity in previous studies DNA molecular computation usually be used to solve NP-complete continuous path search problems (for example HPP, traveling salesman problem), rarely for NP problems with discrete solutions result, such as the 0-1 knapsack problem, graph coloring problem. In this paper, we present a new algorithm for solving the 0-1 knapsack problem with DNA molecular operations. For 0-1 knapsack problem with n distinct items, weight capacity C and total profits W, we reasonably design fixed length DNA strands representing items, take appropriate steps and get the solutions of the problem in proper length range using O(n + C + W) time. We extend the application of DNA molecular operations and simultaneity simplify the complexity of the computation.
Keywords: DNA biological computing, the 0-1 knapsack problem, Adleman-Lipton model, NP-complete problem
