基于质粒模型的DNA计算机算法求解背包问题

摘要

本研究在穷举法的背包策略的基础上借鉴二表算法的思路，应用求解最大团问题的思路计算DNA计算机的NP完全计算问题。使用这种算法，能将DNA分子计算的维数从60扩大至120，这种算法的DNA链数可达亚指数的O(1414n)，这种算法拓展了穷举法背包策略的限制，使DNA计算机NP完全问题算法优化。%Draw lessons from the thinking of two table algorithm, this study applied thinking in solving the largest group of DNA computer np-complete calculation problem. Using this algorithm, the dimensions of the DNA molecular computation can be expanded from 60 to 120, the number of DNA strands of this algorithm can reach the index , expand the exhaustive method backpack strategy, make the algorithm to optimize DNA computer NP complete problem.