Understanding Tabulation and Dynamic Programming with the Knapsack Problem in JavaScript

The 0/1 Knapsack problem is the classic introduction to Dynamic Programming (DP). Given a set of items, each with a weight and a monetary value, determine the maximum value that can fit within a bag of capacity W.

A brute-force recursive tree explores all (2^n) subsets, causing exponential time complexity. Dynamic Programming solves this in pseudo-polynomial time by caching solutions to overlapping subproblems in a bottom-up tabulation table.

Example #

const values = [60, 100, 120];
const weights = [10, 20, 30];
const capacity = 50;
console.log(knapsack(weights, values, capacity)); // 220 (items 2 & 3)

Implementation #

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // Initialize 1D DP array of size capacity + 1
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < n; i++) {
    const w = weights[i];
    const v = values[i];
    // Traverse backwards to prevent using the same item multiple times
    for (let c = capacity; c >= w; c--) {
      dp[c] = Math.max(dp[c], dp[c - w] + v);
    }
  }

  return dp[capacity];
}

Complexity Analysis #

• Time Complexity: (O(n imes W)) where (n) is the number of items and (W) is capacity.
• Space Complexity: (O(W)) optimized 1D memory array.

Main Point: The 0/1 Knapsack problem demonstrates how bottom-up tabulation replaces exponential recursion with an efficient (O(n imes W)) solution.

Credits #

Photo by Kalist Strzalkowski on Unsplash

← Home