Solving the 0-1 knapsack problem based on a parallel intelligent molecular computing model system

摘要

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.