The knapsack problem asks you to choose items with different weights and values, maximize total value, and stay within a weight limit. Imagine packing a bag before a journey: every item you take uses capacity, but some items are more valuable than others. The simplest version ignores physical size and dimensions. section 4.2
Many combinations can be valid, but they are not equally good. With eight items, there are 256 possible include-or-exclude selections. Possibilities grow rapidly as the item count increases, making the problem useful for illustrating optimization and evolutionary algorithms. section 4.2
A small packing puzzle
With a 9 kg capacity, including items 1, 4, and 6 weighs 8 kg and is worth $8. Including items 1, 3, and 7 weighs 9 kg and is worth $14. Including items 2, 3, and 6 would be worth $15, but weighs 15 kg, so it violates the constraint. The second selection is therefore the best of these examples. section 4.2
Table 4.1 Knapsack weight capacity: 9 kg
|
Item ID |
Item name |
Weight (kg) |
Value ($) |
| 1 |
Pearls |
3 |
4 |
| 2 |
Gold |
7 |
7 |
| 3 |
Crown |
4 |
5 |
| 4 |
Coin |
1 |
1 |
| 5 |
Axe |
5 |
4 |
| 6 |
Sword |
4 |
3 |
| 7 |
Ring |
2 |
5 |
| 8 |
Cup |
3 |
1 |
Compare each item's weight and value in the 9 kg example before evaluating possible combinations. section 4.2
An evolutionary representation uses one binary gene per item: 1 means include it and 0 means leave it out. Candidate solutions must not repeat items and must respect the weight limit. Invalid candidates can be repaired, discarded, or given a severe penalty. Fitness sums included values while also checking total weight; an overweight candidate receives a score of 0. section 4.6 section 4.7
def calculate_individual_fitness(individual, maximum_weight):
total_individual_weight = 0
total_individual_value = 0
for gene_index in range(len(individual)): #A
gene_switch = individual[gene_index]
if gene_switch == '1': #B
total_individual_weight
➥+= knapsack_items[gene_index][KNAPSACK_ITEM_WEIGHT_INDEX] #C
total_individual_value
➥+= knapsack_items[gene_index][KNAPSACK_ITEM_VALUE_INDEX] #C
if total_individual_weight > maximum_weight: #D
return 0
return total_individual_value #E
Trace how a binary candidate accumulates item weights and values, then receives either its value or a zero penalty. section 4.7
