Solving 0-1 Knapsack Problems by Greedy Method and Dynamic Programming Method
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.
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