knapsack problem

The KP problem is an example of a combinatorial optimization problem, which seeks
for a best solution from among many other solutions. It is concerned with a knapsack
that has positive integer volume (or capacity) V. There are n distinct items that
may potentially be placed in the knapsack. Item i has a positive integer volume Vi
and positive integer benefit Bi.


Let Xi determines how many copies of item i are to be placed into the knapsack. The goal is to:Maximize


Example:
a = [2, 3, 6, 12, 25, 50, 100, 200]
s = 139
Steps:
139 < 200 ? x8 = 0
139 > 100 ? x7 = 1 s = 39
39 < 50 ? x6 = 0
39 > 25 ? x5 = 1 s = 14
14 > 12 ? x4 = 1 s = 2
2 < 6 ? x3 = 0
2 < 3 ? x2 = 0
2 = 2 ? x1 = 1 s = 0



A chromosome can be represented in an array having size equal to the number
of the items (in our example of size 4). Each element from this array denotes
whether an item is included in the knapsack (‘1’) or not (‘0’).

Termination conditions
The population converges when either 90% of the chromosomes in the population have the same fitness value or the number of generations is greater than a fixed number.
Fitness function
We calculate the fitness of each chromosome by summing up the benefits of the items that are included in the knapsack, while making sure that the capacity of the knapsack is not exceeded. If the volume of the chromosome is greater than the capacity of the knapsack then one of the bits in the chromosome whose value is ‘1’ is inverted and the chromosome is checked again. Here is a flowchart of the fitness function algorithm: