Dynamic Programming21 sections · 916 units
Open in Course

Lessons from Value-Based Knapsack

When to swap

The key lesson: when one dimension is too large, check if you can swap it with the answer. Standard knapsack: capacity as index, value as answer. Value-based knapsack: value as index, weight as answer (then filter by capacity).

This swap works when the "large" dimension is what you'd normally index by, and the "small" dimension (total value) can become the new index. Look at constraints carefully. They often hint at which formulation to use.