Solving 0-1 Knapsack Problems by Greedy Method and Dynamic Programming Method


Article Preview

The 0-1 knapsack problem is typical problem in computer science and its solution is a hot spot in algorithms design and verification. Because it is very hard to solve, it is very important in the research on cryptosystem and number theory. In this paper, the 0-1 knapsack problem and its algorithm is analyzed firstly. And then this paper presents two kinds of expand form, and proposes two efficient algorithms based on dynamic programming and greedy algorithm to solve the proposed problems. Simulation results show it is effective.



Advanced Materials Research (Volumes 282-283)

Edited by:

Helen Zhang and David Jin




L. Liu, "Solving 0-1 Knapsack Problems by Greedy Method and Dynamic Programming Method", Advanced Materials Research, Vols. 282-283, pp. 570-573, 2011

Online since:

July 2011





[1] Sartaj Sahni. Data Structures, Algorithms, and Applications in C++. China Machine Press, (2008).

[2] Robert Sedgewick. Algorithms In C. China Machine Press, (2008).

[3] Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson Addison-Wesley, Boston, (2006).

[4] Holger Mauch. DP2PN2Solver: A flexible dynamic programming solver software tool. Journal of Control and Cybernetics, (2006).