An Algorithm of 0-1 Knapsack Problem Based on Economic Model

Yingying Tian, Jianhui Lv, Liang Zheng

College of Information Science and Engineering, Northeastern University, Shenyang 110819, China.
School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, China.

DOI: 10.4236/jamp.2013.14006                

Abstract

In order to optimize the knapsack problem further, this paper proposes an innovative model based on dynamic expectation efficiency, and establishes a new optimization algorithm of 0-1 knapsack problem after analysis and research. Through analyzing the study of 30 groups of 0-1 knapsack problem from discrete coefficient of the data, we can find that dynamic expectation model can solve the following two types of knapsack problem. Compared to artificial glowworm swam algorithm, the convergence speed of this algorithm is ten times as fast as that of artificial glowworm swam algorithm, and the storage space of this algorithm is one quarter that of artificial glowworm swam algorithm. To sum up, it can be widely used in practical problems.

Keywords

0-1 Knapsack; Economic Model; Optimization Algorithm; Storage Space

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. A. Razborov, “On Provably Disjoint NP-Pairs. Electronic Colloquium on Computational Complexity,” Technical Report TR, 1994, pp. 94-006.
[2]	E. Maslov, “Speeding up Branch and Bound Algorithms for Solving the Maximum Clique Problem,” Journal of Global Optimization, 2013, pp. 1-12.
[3]	H. Fouchal and Z. Habbas, “Distributed Backtracking Algorithm Based on Tree Decomposition over Wireless Sensor Networks,” Concurrency Computation Practice and Experience, Vol. 25, No. 5, 2013, pp. 728-742. http://dx.doi.org/10.1002/cpe.1804
[4]	G. Lantoine, “A Hybrid Differential Dynamic Programming Algorithm for Constrained Optimal Control Problems,” Journal of Optimization Theory and Applications, Vol. 154, No. 2, 2012, pp. 418-423. http://dx.doi.org/10.1007/s10957-012-0038-1
[5]	F. Zhou, “A Particle Swarm Optimization Algorithm,” Applied Mechanics and Materials, 2013, pp. 1369-1372.
[6]	K.-S. Yoo, “A Modified Ant Colony Optimization Algorithm for Dynamic Topology Optimization,” Computers and Structures, Vol. 123, 2013, pp. 68-78. http://dx.doi.org/10.1016/j.compstruc.2013.04.012
[7]	Z. Y. Yan. “Exact Solutions of Nonlinear Dispersive K(m, n) Model with Variable Coefficients,” Applied Mathematics and Computation, Vol. 217, No. 22, 2011, pp. 9474-9479. http://dx.doi.org/10.1016/j.amc.2011.04.047
[8]	J. H. Lv, “The Experiment Data on 0-1 Knapsack Problem.” http://user.qzone.qq.com/1020052739/infocenter#!app=2&via=QZ.HashRefresh&pos=add
[9]	K. Cheng and L. Ma, “Artificial Glowworm Swarm Optimization Algorithm for 0-1 Knapsack Problem,” Application Research of Computers, Vol. 30, No. 4, 2013, pp. 993-995.