liveBook · Manning

Knapsack algorithm

As explained in Algorithms Every Programmer Should Know

The knapsack framework is an optimization approach for selecting indivisible items under a resource capacity while maximizing an associated value.

The knapsack algorithm selects a highest-value subset of indivisible items without exceeding a capacity or budget. Each item is an all-or-nothing choice: take it or leave it. section 7.0

Testing every combination takes exponential time, O(2ⁿ). Dynamic programming avoids repeating work by tracking earlier decisions and storing solutions for smaller item sets and capacities. section 7.0

Scheduling workloads

With an 8-GB limit, applications needing 1, 2, and 5 GB have priority values 2, 3, and 6. Selecting them uses all 8 GB and gives a total priority of 11. section 7.2

The same framework applies to loading indivisible freight under a vehicle’s payload limit. section 7.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Contrasts exponential brute force with dynamic programming that stores solutions across items and incremental capacities.
Examples
Works through an 8-GB workload-selection case and introduces freight loading under an 800-kg payload limit.
What you can do after
Apply dynamic programming to choose a highest-value subset that stays within a resource ceiling.
How it connects
Connects dynamic programming with overlapping subproblems and optimal substructure.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.