Volume 8 Number 3 (Mar. 2013)
Home > Archive > 2013 > Volume 8 Number 3 (Mar. 2013) >
JCP 2013 Vol.8(3): 669-675 ISSN: 1796-203X
doi: 10.4304/jcp.8.3.669-675

Solution to the 0-1 Knapsack Problem based on DNA Encoding and Computing Method

Lian Ye and Min Zhang
Department of Computer, Chongqing University, Chongqing, China

Abstract—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 NPcomplete 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.

Index Terms—0-1 knapsack problem, DNA computing, Optimization

[PDF]

Cite: Lian Ye and Min Zhang, " Solution to the 0-1 Knapsack Problem based on DNA Encoding and Computing Method," Journal of Computers vol. 8, no. 3, pp. 669-675, 2013.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>