A hybrid algorithm for solving knapsack problem

Author: Maka Labadze
Keywords: knapsack problem, genetic algorithm, dynamic programming.
Annotation:

The paper describes the hybrid method of solving the 0-1 knapsack problem. The 0-1 knapsack problem is the well-known and most intensively studied combinatorial optimization problem, which is NP-hard problem. It has applications in cryptography, capital budgeting, cargo loading, utilization of communication channels, logistical problems. In order to solve the problem, there are exact (branch and bound method, dynamic programming method), as well as heuristic algorithms (genetic algorithms, etc.), Decades of algorithmic improvements have shown that 0-1 knapsack problems have been solved for nearly all standard instances, but for a certain class of instances, the problem is still hard to solve. In this paper we present hybrid algorithm, which is a combination of the genetic algorithm and the dynamic programming method. The knapsack problem for "hard" instances, can not be solved by the method of dynamic programming, while the genetic algorithm can find an approximate solution.The hybrid algorithm proposed by us, improved the approximate optimal solution obtained by the genetic algorithm by the method of dynamic programming. This method is tested for some instances.