Course contentsShow
← Computer Science
Lesson 1924 of 2,87243. Complexity TheoryFree lesson

The Knapsack Problem

Selecting items to maximize value without exceeding weight capacity, an NP-complete decision problem.

The Knapsack Problem

You'll learn: How the Knapsack Problem asks you to pack items optimally under a weight constraint, making it a classic NP-complete challenge.

The Core Challenge

Imagine you're packing for a camping trip with a backpack that holds at most 50 pounds. You have items—tent (20 lbs, 100value),sleepingbag(10lbs,100 value), sleeping bag (10 lbs, 60 value), food (15 lbs, $80 value), and so on. Each item has a weight and a value. Which items should you pack to maximize total value without exceeding 50 pounds?

This is the Knapsack Problem: given items with weights and values, and a capacity limit, select a subset that maximizes value while staying within the weight constraint.

Why It's NP-Complete

The decision version asks: "Can we achieve at least value V with capacity W?" This problem is NP-complete, meaning:

  • Easy to verify: Given a proposed selection, you can quickly check if it fits and reaches the target value
  • Hard to solve: Finding the optimal selection requires examining many combinations—no known polynomial-time algorithm exists for the general case

The Knapsack Problem reduces to other NP-complete problems (like Subset Sum, which is actually a special case where value equals weight). If you could solve Knapsack efficiently, you could solve all NP problems efficiently—which we believe is impossible.

Practical Relevance

Unlike some theoretical problems, Knapsack appears everywhere: budget allocation, cargo loading, resource management, investment portfolios. While it's NP-complete in theory, dynamic programming provides pseudo-polynomial solutions that work well for many real-world instances.

Key Takeaway: The Knapsack Problem—selecting items to maximize value under weight constraints—is NP-complete, capturing the difficulty of optimization problems where verification is easy but finding solutions is computationally hard.