0/1 Knapsack Problem

Fill a knapsack of fixed capacity with items of given weight and value — maximize total value.

Intuition

The "0/1" means each item is fully in or fully out. (If you could split items, a simple greedy by value-per-weight would optimally solve it — but you can't.)

Concrete example (from your notes)

Knapsack capacity K = 13 kg. 13 items:

Naive: take O1 + O2 = 12 kg (960 $), then fit one O11 (1 kg, 2 $) → total 962 $.

Better: take O1 (6) + O3 (2) + O4 (2) + O8 (3) = 13 kg → 480+158+158+233 = 1029 $. 🏆

This shows why simple greedy isn't enough — you need to consider combinations.

4 construction methods

All four follow the same skeleton:

Sort items by some criterion.
weight = 0; value = 0
for each item i (in sorted order):
    if weight + w[i] <= K:
        put i in the bag
        value += v[i]; weight += w[i]

None of these is guaranteed optimal. Sorting by value/weight ratio is usually best (this is what M4-ratio does in your local search version 5).

Local search — Greedy improvement

Once you have any feasible solution, you can try to improve it by swapping items in and out.

Version 1 — Random swap, accept if gain > 0

while (not stop):
    pick random item X in the bag
    pick random item Y not in the bag
    if (swap X↔Y is feasible) and (new value > old value):
        accept the swap

Version 2 — Swap OR migrate

while (not stop):
    choice = random 0 or 1
    if choice == 0:    # swap
        same as Version 1
    else:              # migrate (add an item if there's room)
        pick random X not in bag
        if (weight + w[X] <= K):
            add X to the bag

Version 3 — Swap and repair

while (not stop):
    swap (X in, Y out)  // ignore feasibility for now
    if new value > old value:
        accept the swap

# Repair phase
while (weight > K):
    remove the lowest-value item from the bag

Version 4 — Best swap / best migration (not random)

Like Version 2 but instead of random X and Y, pick the best X and Y that maximize the gain.

Version 5 — Ratio-based

while (not stop):
    X ← item OUTSIDE bag with the highest value/weight ratio
    Y ← item INSIDE  bag with the lowest value/weight ratio
    if (swap X↔Y is feasible) and (new value > old value):
        accept it.

Interactive demo

Tweak items and capacity, then try the methods.

Exam tips