The Knapsack Problem

We are given a set of $n$ objects with weight $w_i$ and cost $c_i$. The goal of the knapsack problem is to find a subset of these object with the maximum cost (sum of costs of the objects in the set) such that the sum of the weights of the objects is less than a specified limit $W$.

You task is to implement an evolutionary algorithm that solves this problem. You can start you implementation from scratch, or you can use some of the implementations we created in the practicals.

There are four input files for you to experiment with. Each of the files contains a number of lines – the first line contains two number – the number of objects $n$ and the knapsack capacity $W$. Then, $n$ lines follow, each of them containing the cost $c_i$ and weight $w_i$ of a single object. The values on a single line are delimited by spaces.

For the two input files debug_10.txt and debug_20.txt, the optimum solutions (costs) are 295 and 1024 respectively. Your goal is to try to find the solutions for the files input_100.txt and input_1000.txt.

Send me an e-mail (to Martin.Pilat@mff.cuni.cz) that contains the description of your algorithm – the individual encoding, the genetic operators/selection you used, etc. Additionally include a plot of how the fitness changes with increasing number of generations and what was the best solution you found.

Deadlines:

The deadline for the assignment is April 4, 2023.