首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Solution to the 0/1 Knapsack Problem Based on Dna Computing
  • 本地全文:下载
  • 作者:Anirban De Sarkar ; Miss Sanchita Paul
  • 期刊名称:Journal of Theoretical and Applied Information Technology
  • 印刷版ISSN:1992-8645
  • 电子版ISSN:1817-3195
  • 出版年度:2008
  • 卷号:4
  • 期号:06
  • 出版社:Journal of Theoretical and Applied
  • 摘要:

    A lot of current research in DNA computing has been directed towards solving hard combinatorial problems. Among them Knapsack problem is one of the most common problems which have been studied intensively in the last decade attracting both theorists and practicians. Fractional Knapsack Problem is easily solvable by greedy strategy, but 0/1 Knapsack Problem is not possible to solve in this method. In this paper we have described a DNA computing model to find the optimal solution of 0/1 Knapsack problem. Here we have used a unique strategy to encode data inside DNA. We have replicated the DNAs and in the later stage took the combination of each and every DNA to form double stranded DNAs in order to find out the optimal solution. This method is a clear evidence for the ability of DNA computing solving hard numerical optimization problems, which is not a very easy work to solve with the help of traditional electronic computers.

  • 关键词:DNA Computing;Knapsack Problems;Numerical Optimization;Electronic Computers
国家哲学社会科学文献中心版权所有