2012 | OriginalPaper | Buchkapitel
A DNA Computing Algorithm for Solving the Knapsack Problem
verfasst von : Lian Ye
Erschienen in: Information and Business Intelligence
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Knapsack problem is a classical NP-Complete problem. In this paper, a DNA computing algorithm is proposed to find out the optimal solution of 0-1 knapsack problem. The DNA encoding method is described to translate the weight and value of items into DNA stands. Then replicated the stands and took the combination of every DNA stand to form double stranded DNA sequences in order to find out the optimal solution. The proposed DNA encoding method is an improvement on the previous ones, and it provides further evidence for the ability of DNA computing to solve numerical optimization problems.