关键词: DNA计算 收缩背包问题 链接反应 凝胶电泳 DNA探针 放射自显影

Abstract:

The collapsing knapsack problem （CKP） is the transformation of the standard knapsack problem （SKP）. The capacity of its knapsack is the non-increa   sing function of the number of items loaded in it. A novel algorithm based on DNA computing is proposed, which solves the collapsing knapsack problem. F   irstly, we partition the constraint of CKP into several different constraints. Secondly, we design some oligonucleotides corresponding to the weight of    the items and some ligation splints which are mixed together in a single ligation reaction to produce the DNA links representing all random combinations  of the items. Thirdly, we perform a series of biochemical experiments to obtain the feasible solutions. Finally, we get the optimal solutions to the given problem by comparing the target-function＇s values of those feasible solutions.

Key words:  （DNA computing, collapsing knapsack problem, ligature, gel electrophoresis, DNA probe;auto , radiography）