0/1 Knapsack

optimizationsubset-selectionclassic

Press play to start

1function knapsack(capacity: number, weights: number[], values: number[]): number {
const n = weights.length
const dp = Array.from({ length: n+1 }, () => Array(capacity+1).fill(0))
for (let i = 1; i <= n; i++) {
  for (let w = 0; w <= capacity; w++) {
    if (weights[i-1] <= w) {
      dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
    } else {
      dp[i][w] = dp[i-1][w]
    }
  }
}
return dp[n][capacity]
14}

Step 1/0

Custom array:

Complexity

Best:O(n·W)
Average:O(n·W)
Worst:O(n·W)
Space:O(n·W)

Description

Finds the maximum value subset of items that fits in a weight-capacity knapsack, where each item can be taken or left.

When to use

Resource allocation, budget optimization, cargo loading. Classic DP problem with many real-world variants.