Math
Knapsack: greedy against the table
Choose numbered cargo under a mass limit. Compare your selection with greed and the exact solution, open a table cell and trace the optimal set backwards.
What happens
Choose numbered cargo under a mass limit. Compare your selection with greed and the exact solution, open a table cell and trace the optimal set backwards. T(i,c): best value using only the first i items and capacity c. Click a cell; blue skips, green takes. Arrows page through a large table. w = weight, v = value. Cargo size is decorative; only total weight limits the bag. Fractional is an upper bound for a different task where items may be cut. It is not another feasible 0/1 selection.
Equations used in the module
Equations
0/1: sum(w_i x_i) <= W; max sum(v_i x_i), x_i in {0,1}
T(0,c) = 0
w_i > c: T(i,c) = T(i-1,c)
w_i <= c: T(i,c) = max(T(i-1,c), v_i + T(i-1,c-w_i))
v_i/w_i ↓; i ↑
F_greedy <= F_0/1 <= F_fractional
V_single = max({0} ∪ {v_i : w_i <= W})
max(F_greedy, V_single) >= F_0/1 / 2
N_DP = n*W; N_subsets = 2^n
