Solving the 0-1 Knapsack Problem by Using Tissue P System With Cell Division

Abstract

Membrane computing is a kind of distributed and parallel computing model inspired by a biological cell mechanism. The maximum parallelism of membrane computing improves the computational efficiency of its computational model. In this paper, a tissue P system named Π KP is proposed to solve the 0-1 knapsack problem, which is one of the classic NP-hard problems. Π KP could obtain the accurate solutions of knapsack problem and points out the number of accurate solutions, which mainly consists of three stages: first, generate all the solutions of knapsack problem by a cell division; then calculate the weights and total values in all the candidate membranes, which will be kept or dissolved according to the restriction of knapsack problem; and check out the final solutions. The instances are executed on a membrane simulator named UPSimulator, and the result of the experiments shows the whole searching procedure by the rules and proves the correctness and efficiency of the system.