An Algorithm of Solving 0-1 Knapsack Problem
Liang Dao-lei · Computer Technology and Development · 2013
Intelligent search algorithm may not find the optimal solution of the problem and may exit the phenomenon of the local convergence.The time complexity of dynamic programming,backtracking,branch and bound method is relatively high.In order to solve these problems,analyze the mathematical model of the 0-1 knapsack problem,and discuss the structure characteristics of the optimal solution.At the same time,it establishes the recurrence relation which is used to solve the optimal value of the 0-1 knapsack problem.According to the recurrence relation,put forward an algorithm to solve the 0-1 knapsack problem and code the algorithm by using C++.Its time complexity is O(min{nW,2n}).Three groups of different size data are inputted in the algorithm.Their output results show that the algorithm is high efficiency and can always get the optimal solution of the problem.