Knapsack

Given a set of \( N \) items, each with a value \( v_i \) and a vector of weights \( \mathbf{w}_i = (w_{i,1}, w_{i,2}, \dots, w_{i,D}) \) across \( D \) capacity dimensions, choose a binary subset \( x = (x_1, x_2, \dots, x_N) \) that maximises the total value while respecting every capacity \( C_d \):

\[ \max_{x \in \{0,1\}^N} \sum_{i=1}^{N} v_i x_i \quad \text{subject to} \quad \sum_{i=1}^{N} w_{i,d}\, x_i \le C_d,\ \forall d \in \{1,\dots,D\} \]

When \( D = 1 \) this is the classic 0/1 knapsack (one capacity, one weight per item). When \( D \ge 2 \) it becomes the multi-dimensional knapsack, useful when every item charges against several budgets at once (weight and volume, budget and headcount, CPU and RAM).

Fitness adds a penalty for any over-capacity: \( f(x) = \sum_i v_i x_i - \lambda \sum_d \max\!\left(0,\; \sum_i w_{i,d} x_i - C_d\right) \). The penalty weight \( \lambda \) defaults to 1000 so any feasible solution beats any infeasible one.