An Evolutionary Solution to the 0/1 Knapsack Problem Using Elitist Genetic Algorithm

The knapsack problem is a classic optimization problem in computer science. It includes selecting a subset of items from a given set of items each with weights and corresponding values and a given capacity and the weights have to be selected in such a way that they will not exceed the given capacity giving the maximum profit. Typically, the brute force approach takes a significant amount of time (with exponential time complexity). In this work, an attempt is made to solve this problem using an elitist genetic algorithm. The obtained outcomes are compared with three different approaches basic genetic algorithm, brute force approach, and dynamic programming. The proposed approach, as an evolutionary method, evaluates the total weight and value of all possible subsets, then selects subsets with the highest value that are still below the weight limit, but also have limitations. It appears that the experimental results are sufficiently promising.