0 1 Knapsack Problem in DSA Typescript

Mental Model

We want to pick items with weights and values to maximize value without exceeding a weight limit. Each item can be chosen only once.

Analogy: Imagine packing a backpack for a trip. You have limited space (weight limit) and many items with different usefulness (value). You want to pack the most useful combination without overloading.

Backpack capacity: 5
Items:
[Item1: weight=2, value=3]
[Item2: weight=3, value=4]
[Item3: weight=4, value=5]

Backpack (capacity slots): [ ] [ ] [ ] [ ] [ ]
We try to fill these slots with items without exceeding capacity.

Dry Run Walkthrough

Input: items: [(weight=2, value=3), (weight=3, value=4), (weight=4, value=5)], capacity=5

Goal: Find the maximum total value of items that fit in the backpack without exceeding capacity 5

Step 1: Start with no items, capacity 0 to 5, all values 0

DP table rows: items 0 to 3, columns: capacity 0 to 5
Row 0 (no items): 0 0 0 0 0 0

Why: Base case: no items means no value regardless of capacity

Step 2: Consider item 1 (weight=2, value=3), update DP for capacities 0 to 5

Row 1:
Capacity 0,1: 0 (item too heavy)
Capacity 2-5: max of not taking or taking item 1
Values: 0 0 3 3 3 3

Why: If capacity >= 2, we can take item 1 and get value 3

Step 3: Consider item 2 (weight=3, value=4), update DP for capacities 0 to 5

Row 2:
Capacity 0-2: same as row 1
Capacity 3: max(3,4)=4
Capacity 4: max(3,4)=4
Capacity 5: max(3,3+4)=7

Why: At capacity 5, taking item 2 plus item 1 (capacity 2) gives value 7

Step 4: Consider item 3 (weight=4, value=5), update DP for capacities 0 to 5

Row 3:
Capacity 0-3: same as row 2
Capacity 4: max(4,5)=5
Capacity 5: max(7,5)=7

Why: At capacity 5, best is still 7 from previous items

Result:

DP table last row: 0 0 3 4 5 7
Maximum value achievable: 7

Annotated Code

DSA Typescript

class Item {
  constructor(public weight: number, public value: number) {}
}

function knapsack01(items: Item[], capacity: number): number {
  const n = items.length;
  const dp: number[][] = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const { weight, value } = items[i - 1];
    for (let w = 0; w <= capacity; w++) {
      if (weight > w) {
        dp[i][w] = dp[i - 1][w]; // can't take item i
      } else {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight] + value); // max of taking or not
      }
    }
  }

  return dp[n][capacity];
}

// Driver code
const items = [new Item(2, 3), new Item(3, 4), new Item(4, 5)];
const capacity = 5;
const maxValue = knapsack01(items, capacity);
console.log(maxValue);

for (let i = 1; i <= n; i++) {

iterate over items to build DP table row by row

for (let w = 0; w <= capacity; w++) {

iterate over all capacities from 0 to max capacity

if (weight > w) { dp[i][w] = dp[i - 1][w]; }

if item weight exceeds current capacity, skip item

else { dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight] + value); }

choose max value between skipping or taking the item

Output

7

Complexity Analysis

Time: O(n * capacity) because we fill a table with n items and capacity columns

Space: O(n * capacity) because we store results for each item and capacity combination

vs Alternative: Compared to brute force exponential approach, DP reduces time drastically by storing intermediate results

Edge Cases

empty items list

returns 0 as no items to choose

DSA Typescript

const n = items.length;

capacity zero

returns 0 as no capacity to carry items

DSA Typescript

for (let w = 0; w <= capacity; w++) {

items heavier than capacity

items skipped, result 0 if none fit

DSA Typescript

if (weight > w) { dp[i][w] = dp[i - 1][w]; }

When to Use This Pattern

When you need to pick items with weights and values to maximize value without exceeding a limit, use 0 1 Knapsack DP to efficiently find the best combination.

Common Mistakes

Mistake: Not checking if item weight fits current capacity before taking it
Fix: Add condition to skip item if weight > current capacity

Mistake: Using 1D array without careful update order causing incorrect results
Fix: Use 2D DP or update 1D array backwards to avoid overwriting needed values

Summary

Finds the max value of items fitting in a capacity-limited knapsack with each item chosen once.

Use when selecting items with weights and values to maximize total value without exceeding capacity.

The key is building a table of best values for each item and capacity step by step.