Knapsack Problem
A classic optimization problem for selecting items with weights and values to maximize value under a capacity limit
The Knapsack Problem is a classic optimization problem in which a set of items, each with a weight and a value, must be selected to maximize total value without exceeding a fixed weight capacity.
Definition
The Knapsack Problem is a classic optimization problem in which a set of items, each with a weight and a value, must be selected to maximize total value without exceeding a fixed weight capacity.
Overview
The knapsack problem gets its name from the intuitive scenario of a hiker packing a bag with limited capacity, choosing among items of varying weight and usefulness to maximize the total value carried. Despite its simple framing, it's a foundational problem in combinatorial optimization because it illustrates the difference between problems that are efficiently solvable and those that are not, depending on subtle variations in how the problem is defined. The most commonly taught variant, 0/1 knapsack, requires each item to be either fully included or excluded — no partial items and no duplicates. It's solved with dynamic programming using a table indexed by item count and remaining capacity, where each cell represents the best achievable value considering a subset of items up to a given weight limit; this gives a pseudo-polynomial time complexity of O(n·W), where n is the number of items and W is the capacity. The word "pseudo-polynomial" is important: the running time is polynomial in the numeric value of W, not in the number of bits needed to represent W, and 0/1 knapsack is in fact NP-complete in the general sense, meaning no known algorithm solves it in time truly polynomial in the input's bit-length for arbitrarily large capacities. Several variants extend the base problem: fractional knapsack allows taking partial amounts of an item and is solved optimally and efficiently with a simple greedy strategy of taking items in order of value-to-weight ratio, in contrast to 0/1 knapsack where greedy strategies don't guarantee an optimal answer. Unbounded knapsack allows unlimited copies of each item. Beyond its role as a teaching problem, knapsack-style optimization appears directly in resource allocation problems such as budget allocation across competing projects, cargo loading and logistics, portfolio selection under a fixed capital constraint, and cutting stock problems in manufacturing, making it one of the more practically relevant classic algorithms problems rather than a purely academic exercise.
Key Concepts
- Selects items with weight and value to maximize value under a fixed capacity
- 0/1 variant: each item either fully included or excluded, no duplicates
- Solved via dynamic programming with a table indexed by item count and capacity
- Pseudo-polynomial O(n·W) time complexity, not truly polynomial in input size
- 0/1 knapsack is NP-complete in its general formulation
- Fractional knapsack variant solved optimally with a greedy value-to-weight strategy
- Unbounded knapsack variant allows unlimited copies of each item
- Greedy approaches fail to guarantee optimality for the 0/1 variant
Use Cases
Frequently Asked Questions
From the Blog
What Is a Problem Statement? A Practical How-To Guide
A problem statement is a concise description of an issue that needs solving, written so a team can align on what to fix before jumping to solutions. This guide explains its structure and how to write one well.
Read More Career GrowthProblem Solving Skills: How to Build and Show Them
Problem solving is the ability to define a problem clearly, generate options, and choose a workable solution under real constraints. This guide breaks down the process into steps you can practice and demonstrate at work.
Read More Data ScienceHow to fix the small files problem in a data lake
Queries slow down when a table is split across a very large number of small files, because per-file overhead — listing, opening, reading metadata, scheduling a task — starts to dominate the actual reading. Fix it in order: partition cardinality first, writer parallelism second, compaction third.
Read More ProgrammingHow to design API error responses with problem details
Give every error in your API one shape that tells a client three things: which class of failure it is, what specifically was wrong, and whether retrying could help. This article covers the problem details fields, stable error types, field-level validation and what must never leak.
Read More