近年来,随着生物技术的飞速发展,一个新的研究领域——DNA计算随之产生。DNA计算是一种新的计算模式,它以DNA(deoxyribonucleicacid,脱氧核糖核酸)为“原料”,以生化实验为工具进行计算。由于DNA计算机所具有的巨大并行性、海量存储以及低能耗等优点,因此将有望在某些领域弥补现有电子计算机的不足。自1994年美国南加州大学的Adleman教授用生化实验解决了七个顶点的有向哈密尔顿路径问题(Directed Hamilton Path Problem,DHPP)以来,有关DNA计算的科研工作迅速在许多国家展开。虽然已取得了可喜的成果,但有许多经典的图论问题、数学问题等还未有DNA算法;有些问题虽有DNA计算方法,但仍有可改进之处。粘贴系统是建立在粘贴运算基础上的语言生成器,也是一种遵循Watson-Crick互补性质进行退火操作的DNA计算抽象模型。粘贴模型所使用的DNA链具有固定的长度,操作时不需要扩展DNA链,也无需酶的参与,而且它的材料在理论上可以重复使用。因此,有关粘贴模型的研究开展得比较快,许多问题的粘贴DNA算法也被相继提出。由于粘贴模型仅采用原有的四种基本操作,实验操作步骤较多,耗费了大量时间,本文求解问题时采用了多级分离装置,可以实现DNA计算中的多种基本操作,并能实现“多级分离”操作,大大减少实验步骤,成倍提高解题效率。本文介绍了基于表面的DNA计算求解0-1整数规划问题的算法,并且在此算法的基础上把未知数的取值范围扩充到从-2到+2的范围,从而扩展了此表面算法的适用范围。定义了两种约束补链,给出了求解此类整数规划问题的DNA表面计算求解算法。本文给出了一个实例的求解步骤,证明此算法的思想和可行性。本算法中采用荧光猝灭的有关技术,通过观察荧光来排除非解,具有读解、编码简单和错误率低的特点。运用此种增加变量的方法来代替未知数的取值思维方法同样可以适用未知数取+3,-3,+4,-4……等的规划问题中。本文应用多级分离技术解决了以下两个问题:(1)0-1整数规划问题。文中给出了利用多级分离装置基于溶液求解0-1整数规划问题的DNA算法。此种解法克服了表面求解方法的编码和荧光数受限的缺点,且使用了多级分离操作,大大减少实验步骤,成倍提高解题效率。(2)背包问题。本文给出了背包问题的一种新解法,即将其转化为0-1整数规划问题进行求解,在求解中利用了多级分离装置,使实验步骤减少,解题效率提高。在解决以上两个问题时,文中都给出了具体的实例,并通过模拟试验得到了具体的解决方案,说明了算法的可行性和有效性。