0/1背包问题的DNA计算

0/1 Knapsack Problem Based on DNA Computing

0/1背包问题是一个著名NP———复杂问题,以前人们主要用分支———限界法、贪心法等方法去解决该问题。本文主要论述了一种新的计算模式———DNA计算来解决0/1背包问题。依据分子生物学的实验方法,文中所提出的算法是有效和可行的。

0/1 Knapsack Problem is a famous NP hard problem,which used to be solved with Braneh and Bound traversal and Greedy Methodetc. This paper mostly discusses a new computing paradigms DNA Computing, to solve the 0/1 Knapsack Problem. On the basis of the experiment method of bio- molecular, the algorithm is an effective method in this paper.