0/1 Knapsack Problem

In the previous lesson, we solved the Longest Increasing Subsequence (LIS) and learned how Dynamic Programming helps us make optimal choices step by step.

Now we arrive at one of the most famous Dynamic Programming problems used in academics, interviews, and real-world systems: the 0/1 Knapsack Problem.

Understanding the Knapsack Idea

Imagine you have a bag (knapsack) with a fixed weight capacity.

You are given items, each with a weight and a value.

Your goal is simple: maximize total value without exceeding the bag’s capacity.

The rule “0/1” means:

• You either take an item completely (1)
• Or you do not take it at all (0)

You cannot take fractions of an item.

Real-World Example

Suppose you are packing a backpack for a long trip.

You have limited space, so you must choose carefully:

• Laptop (high value, heavy)
• Camera (medium value, medium weight)
• Books (low value, heavy)

You want the best combination, not just the lightest or most expensive item.

Why Greedy Does Not Work

A greedy approach might say: “Pick the most valuable item first.”

But this can fail.

Sometimes, two medium-value items together give more total value than one high-value item.

This is why Dynamic Programming is required.

Defining the Subproblem

Let dp[i][w] represent:

The maximum value using the first i items with a knapsack capacity of w.

This definition allows us to explore all valid choices systematically.

Knapsack Recurrence Relation

For each item i:

If the item’s weight is greater than w:

We cannot include it, so dp[i][w] = dp[i-1][w]

Otherwise:

We choose the better of:

• Excluding the item
• Including the item and adding its value

dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])

Dynamic Programming Implementation

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],
                    values[i-1] + dp[i-1][w - weights[i-1]]
                )
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5

knapsack(weights, values, capacity)

Understanding the DP Table

Rows represent items.

Columns represent knapsack capacity.

Each cell stores the best value possible for that combination.

The final answer is found at the bottom-right cell.

Time and Space Complexity

Time Complexity: O(n × W)

Space Complexity: O(n × W)

Where n is the number of items and W is the capacity.

Why Knapsack Is So Important

This problem teaches:

• Decision making under constraints
• Trade-offs between choices
• Foundation for many optimization problems

It is also the base for resource allocation systems, budget planning, and scheduling.

Mini Practice

Think carefully:

• Why does dp use previous row values?
• What happens if capacity is very large?

Exercises

Quick Quiz

The 0/1 Knapsack problem is one of the strongest foundations for mastering Dynamic Programming.

In the next lesson, we will explore Dynamic Programming in Optimization and see how these ideas scale further.