Multi-Dimensional Knapsack — Multiple Constraints

2D example

int[][] dp = new int[W + 1][V + 1];
for (int i = 0; i < n; i++)
  for (int w = W; w >= weight[i]; w--)
    for (int v = V; v >= volume[i]; v--)
      dp[w][v] = Math.max(dp[w][v], dp[w - weight[i]][v - volume[i]] + value[i]);

Curse of dimensionality

Each new dimension multiplies state space. 3+ dimensions often need pruning/approximation.

Applications

Cloud resource allocation (CPU + RAM + disk). Cargo packing (weight + volume + fragility class).

Approximations

FPTAS exists for constant dimensions. For high-dim, LP relaxation + rounding.