Branch-and-Bound and Dynamic Programming Approaches for the Knapsack Problem

The knapsack problem is one of the most popular NP-hard problems in combinatorial optimization. For 0-1 Knapsack Problem, there are two common approaches which guarantee the optimality of the solutions: Branch-and-Bound (BnB) and Dynamic Programming (DP) algorithms. Both algorithms suffer from a large amount of redundant calculations. To handle this problem, we proposed modifications of these algorithms. For DP, we suggest some new pre-processing and search rules which help us to avoid unneeded calculations. For BnB, we develop a combination of common BnB method with DP with list approach. Computational experiments on artificially generated data and common benchmarks show the effectiveness of the proposed algorithms.