0/1 Knapsack Problem
What you'll learn: How to maximize the total value of items you pack when each item can only be taken once and you have a weight limit.
The Core Idea
Imagine you're packing a backpack for a trip, but it can only hold 10 kg. You have several items, each with its own weight and value (importance to you). You can either take an item completely or leave it behind—no partial packing allowed. That's the 0/1 part: each item is either included (1) or excluded (0).
The 0/1 Knapsack Problem asks: Which items should you choose to maximize total value without exceeding the weight capacity?
Why Dynamic Programming?
This problem has both key DP properties:
- Optimal Substructure: The best solution for packing n items uses solutions from packing fewer items
- Overlapping Subproblems: When deciding about item i, you repeatedly need answers for the same smaller weight limits
The Decision Framework
For each item, you face a choice:
- Include it: Get its value, but reduce remaining capacity
- Exclude it: Keep current capacity for other items
You pick whichever gives higher total value.
State Definition
dp[i][w] = maximum value using first i items with weight limit w
The transition:
- If item i is too heavy:
dp[i][w] = dp[i-1][w] - Otherwise:
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])
This differs from the Fractional Knapsack (which used greedy): here you cannot take part of an item, forcing you to explore all combinations through DP.
Key Takeaway: The 0/1 Knapsack Problem uses dynamic programming to optimally select whole items under a weight constraint, building solutions by deciding whether to include or exclude each item based on previously computed subproblems.