Course contentsShow
← Computer Science
Lesson 930 of 2,87222. Dynamic ProgrammingFree lesson

0/1 Knapsack Problem

Maximize value by selecting items with weight limit where each item can be taken at most once.

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:

  1. Optimal Substructure: The best solution for packing n items uses solutions from packing fewer items
  2. 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.