文章基本信息

标题：Solution to the 0-1 Knapsack Problem based on DNA Encoding and Computing Method
本地全文：下载
作者：Ye, Lian ; Zhang, Min
期刊名称：Journal of Computers
印刷版ISSN：1796-203X
出版年度：2013
卷号：8
期号：3
页码：669-675
DOI：10.4304/jcp.8.3.669-675
语种：English
出版社：Academy Publisher
摘要：DNA computing is a new computational paradigm that executes parallel computation with DNA molecules. Some researches in DNA computing have been presented to solve computational problems such as NP-complete problems in polynomial increasing time by using its super parallel and high density power. Among them knapsack problem is one of the most common problems which have been studied intensively in the last decade attracting both theorists and practicing. This paper proposes an encoding and computing method to solve 0-1 knapsack problem. The encoding method is described to generate superior DNA strands with fewer errors according to the characteristics of DNA sequences. Then the computing algorithm replicate the strands which expressed as the weight of items and take the combination of every DNA strand to form double stranded DNA sequences in order to find out the optimal solution. The results demonstrate the superiority of our approach which may be used to resolve different NP-hard problems by adjusting the DNA-based procedures.
关键词：0-1 knapsack problem;DNA computing;Optimization