A Linear-Time Solution to the Knapsack Problem Using P Systems with Active Membranes
A Linear-Time Solution to the Knapsack Problem Using P Systems with Active Membranes
复制标题
DOI：
10.1007/978-3-540-24619-0_19
复制
发表时间：
2003-07
期刊：
影响因子：
--
通讯作者：
M. Pérez-Jiménez;A. Riscos-Núñez
中科院分区：
文献类型：
--
作者：
M. Pérez-Jiménez;A. Riscos-Núñez
到目前为止，文献中很少考虑处理数值问题的P系统。在本文中，我们提出了一个有效的解决方案，背包问题，使用家庭的确定性P系统的活动膜使用2-分裂。我们表明，任何计算的步骤的数量是线性顺序，但多项式时间需要预计算资源。
Up to now, P systems dealing with numerical problems have been rarely considered in the literature. In this paper we present an effective solution to the Knapsack problem using a family of deterministic P systems with active membranes using 2-division. We show that the number of steps of any computation is of linear order, but polynomial time is required for pre-computing resources.