摘 要：DNA计算机研究的重要内容是关于如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数。本文将分治策略应用于背包问题的DNA分子计算中，提出了一种新的DNA计算机求解背包问题的算法。背包问题的算法由咒位并行减法器、咒位数据搜索器和其他的4个子算法组成。

关键词：背包问题；DNA计算；计算机

中图分类号：TP301 文献标识码：A 文章编号：1007-9599 （2013） 04-0000-02

1 引言

背包问题可描述如下：给定q个正整数的集合W=（w1，w2，……，wn）和正整数M，要求决定二值q元组X=（x1，x2，……，xq）的值，使得式：被满足。文献[5]设计了基于粘贴模型的n位并行DNA比较器和n位并行加法器来求解背包问题。该算法证明可通过DNA计算来完成复杂的数学运算，而且极大提高了运算的并行度[5]。背包问题属于经典的NP完全问题。信息密码学和数论研究中都经常具有NP问题。Perez-Jimenez等人针对背包问题提出了基于粘贴模型的DNA计算机算法。在2004年的时候，Chang等人针对背包问题设计一种编码错误更少的DNA计算机算法。但是上述DNA计算机算法都属于简单的穷举算法。并不能真正有效的解决背包问题。由于本分需要分析的就是关于分治的背包问题DNA计算机算法，因此建这种方法代入到背包问题DNA计算机算法设计中，运用一种全新的背包问题DNA计算机算法。经过运算发现代入分治背包方法可以有效的对这类问题进行运算，并提高运算的准确率。

2 分治法的背包问题的DNA计算机算法

2.1 DNA计算机算法思想

在出现和使用分治解决背包问题的BNA计算机算法之前，Horowitz和Sahni提出的著名二表法是最精确的计算方法。