liveBook · Manning

Knapsack problem

As explained in Timeless Algorithms, The Foundational Ideas

An optimization problem that selects items to maximize total value subject to a capacity constraint.

The 0/1 knapsack problem selects indivisible items to maximize total value without exceeding a fixed capacity. Each item has a weight and value; it must be taken whole or not at all. The same structure models choices such as selecting projects under a budget. section 6.2

Let V(i, c) be the greatest value attainable using the first i items at capacity c. For item i with weight wᵢ and value vᵢ, excluding it gives V(i − 1, c); including it, when wᵢ ≤ c, gives vᵢ + V(i − 1, c − wᵢ). Choose the greater feasible value. The zero-item and zero-capacity cases provide base values of zero. section 6.2.1

Dynamic programming fits because recursive decisions revisit the same states (i, c), and each state's optimum follows from optimal solutions to smaller states. Tabulation computes each distinct state once and reuses it. Greedy choices can miss the global optimum; exhaustive enumeration guarantees it but becomes impractical as item counts grow. section 6.2 section 6.2.1

Capacity seven

For items with (weight, value) pairs (3, 4), (4, 5), (2, 3), and (1, 2), a bottom-up table evaluates each item across capacities zero through seven. Its final value is V(4, 7) = 10. section 6.2.5

Table 6.5 Evaluating Item 4 and completing the solution. The bottom-right cell, 𝑉(4, 7) = 10, gives the maximum value attainable with all four items available and a capacity of 7.
Item (𝑖)
(𝑤𝑖, 𝑣𝑖)
𝑐 = 0
𝑐 = 1
𝑐 = 2
𝑐 = 3
𝑐 = 4
𝑐 = 5
𝑐 = 6
𝑐 = 7
0
Base Cases
0
0
0
0
0
0
0
0
1
(3, 4)
0
0
0
4
4
4
4
4
2
(4, 5)
0
0
0
4
5
5
5
9
3
(2, 3)
0
0
3
4
5
7
8
9
4
(1, 2)
0
2
3
5
6
7
9
10

The completed table shows the optimal value at each capacity after all four items are considered. section 6.2.5

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines the state recurrence, verifies dynamic-programming prerequisites, and works through a bottom-up table.
Examples
Uses four weighted-value items, capacity seven, and a table whose final optimum is ten.
What it assumes
Establishes overlapping subproblems and optimal substructure as prerequisites before applying dynamic programming.
What you can do after
Build it from scratch by initializing base cases and tabulating optimal values across items and capacities.
How it connects
Connects dynamic programming to overlapping subproblems, optimal substructure, greedy algorithms, and exhaustive search.

Also explained in

Compare how 6 books explain knapsack problem →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.