Knapsack Problem: Select items to maximize value without exceeding weight capacity.

Problem Description

You have a knapsack with limited weight capacity and a collection of items, each with a weight and value. The goal is to select items that maximize total value without exceeding the weight limit.

This demonstrates why genetic algorithms excel:

• Building blocks: Good item combinations can be inherited
• Crossover value: Mixing two good solutions often produces better offspring
• Selection pressure: Invalid solutions (too heavy) are penalized

Genome Representation

Binary vector where 1 = item included, 0 = item excluded:

[1, 0, 1, 1, 0, 1]  # Items 0, 2, 3, 5 selected

Fitness Evaluation

• If weight ≤ capacity: fitness = total value
• If weight > capacity: fitness = total value - penalty * overage

Usage

iex> Jido.Evolve.Examples.Knapsack.run()
# Evolution progress shown...
# Final solution near optimal value

Expected Results

Converges to near-optimal solution in 50-100 generations, demonstrating how crossover combines good item selections from different parents.