← Lab · Chapter: 4. Constructive heuristics

Knapsack: ratio heuristic versus optimum

The constructive ratio heuristic fills the knapsack by value/weight: follow it item by item and compare its value with the optimum and with the bound of the continuous relaxation. ◀ ▶ one item at a time, “Run” to see them all.