Share This Article:

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

Abstract Full-Text HTML Download Download as PDF (Size:236KB) PP. 31-35
DOI: 10.4236/jamp.2013.14006    3,544 Downloads   5,914 Views   Citations

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Tian, Y. , Lv, J. and Zheng, L. (2013) An Algorithm of 0-1 Knapsack Problem Based on Economic Model. Journal of Applied Mathematics and Physics, 1, 31-35. doi: 10.4236/jamp.2013.14006.

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.

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.