# Genetic Algorithm for a class of Knapsack Problems

arXiv: https://arxiv.org/abs/1903.03494 · HTML: https://mlsanity.com/paper/1903.03494/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2019.

## Built on by (most cited first, 1 of 1)

- [Evolutionary optimization of contexts for phonetic correction in speech recognition systems](https://mlsanity.com/paper/2102.11480/) (2021)

## Abstract (arXiv)

The 0/1 knapsack problem is weakly NP-hard in that there exist pseudo-polynomial time algorithms based on dynamic programming that can solve it exactly. There are also the core branch and bound algorithms that can solve large randomly generated instances in a very short amount of time. However, as the correlation between the variables is increased, the difficulty of the problem increases. Recently a new class of knapsack problems was introduced by D. Pisinger called the spanner knapsack instances. These instances are unsolvable by the core branch and bound instances; and as the size of the coefficients and the capacity constraint increase, the spanner instances are unsolvable even by dynamic programming based algorithms. In this paper, a genetic algorithm is presented for spanner knapsack instances. Results show that the algorithm is capable of delivering optimum solutions within a reasonable amount of computational duration.