论文部分内容阅读
收缩背包问题是标准背包问题的一个扩展，其中背包的容量为所装物品数量的非增函数。本文提出了基于分子生物技术的求解收缩背包问题的DNA算法，首先将其约束条件进行分解；然后设计一系列与物品重量相对应的寡聚核苷酸片断及其链接模板，在链接酶的作用下将它们进行链接反应，生成代表任意物品组合的DNA链；再通过基本的生物操作筛选出可行解；最后比较各个可行解对应的目标函数值，进而得到最优解。