Using Parallel Filtering Algorithms to Solve the 0-1 Knapsack Problem on DNA-based Computing

摘要

It is shown first by Adleman that deoxyribonucleic acid (DNA) strands could be employed towards calculating solution to an instance of the NP-complete Hamiltonian Path Problem (HPP). Lipton also demonstrated that Adleman’s techniques could be used to solve the satisfiability (SAT) problem. In this paper, it is demonstrated how the DNA operations presented by Adleman and Lipton can be used to develop the DNA-based algorithm for solving the 0-1 Knapsack Problem.