Knapsack Problem

The Knapsack Problem is the poster child of Dynamic Programming. Imagine you are a thief with a backpack that can hold a maximum weight. You are standing in front of a collection of items, each with its own weight and value. Your goal is to pack items that maximize total value without going over the weight limit.

Sounds simple right? Pick the most valuable items first and stuff them in. But what if the most valuable item is super heavy and you could fit three smaller items that are worth more combined? That is where it gets tricky — and where DP shines.

0/1 Knapsack vs Unbounded Knapsack

In the 0/1 knapsack, each item can either be taken or left — no partial items and no duplicates. This is the harder and more common variant.

In the unbounded knapsack, you can take as many of each item as you want. This is simpler because there is no constraint on how many times an item is used. We will focus on the 0/1 version here since it is the one you will encounter in interviews and exams.

The DP Table Approach

We build a 2D table where dp[i][w] represents the maximum value using the first i items with a weight limit of w. For each item, we decide: is it better to include it or skip it?

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w];
      if (weights[i - 1] <= w) {
        const include = dp[i - 1][w - weights[i - 1]] + values[i - 1];
        dp[i][w] = Math.max(dp[i][w], include);
      }
    }
  }
  return dp[n][capacity];
}

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack(weights, values, 8));

Step by Step Walkthrough

For each item, we go through every possible weight from 0 to capacity. If the item fits (its weight is less than or equal to the current capacity), we check whether including it gives a better value than skipping it. The max of those two choices goes into the table.

The time complexity is O(n × capacity) and the space is the same. This is pseudo-polynomial because the runtime depends on the numeric value of the capacity, not just the number of bits. For small capacities, it is blazing fast. For huge capacities, consider optimized approaches.