Knapsack Problem Algorithm

You have a bag with a weight limit. You have a pile of items, each with a weight and a value. Which items do you pick to maximize value without exceeding the weight limit?

That's the Knapsack Problem. It shows up everywhere — resource allocation, budget optimization, cargo loading.

Two flavors

0/1 Knapsack: Each item is all-or-nothing. You either take it or leave it. No cutting a gold bar in half.

Fractional Knapsack: You can take fractions of items. This one is easier — a greedy approach (pick by best value-to-weight ratio) solves it. The 0/1 version is the interesting one.

The intuition

For the 0/1 version, you build a table. Each cell answers: "What's the maximum value I can achieve with the first i items and a capacity of w?"

For each item, you have two choices: skip it, or take it (if it fits). You pick whichever gives more value.

The code

function knapsack01(values, weights, capacity) {
    const n = values.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) {
                dp[i][w] = Math.max(
                    dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                );
            }
        }
    }

    return dp[n][capacity];
}

Complexity

• Time: O(n * capacity) — fill every cell in the table.
• Space: O(n * capacity) — the 2D DP table. Can be optimized to O(capacity) with a single row.

Trade-offs

Dynamic programming gives you the exact answer, but the "capacity" dimension matters. If your capacity is 1,000,000, you're building a massive table. For large capacities with few items, branch-and-bound or approximation algorithms might be smarter choices.