Knapsack DP

Brief Overview

Knapsack DP gets its name from the problem faced by someone who has a knapsack, or bag, with constrained space and who wants to fit the most value into such space. More formally, these problems are typically presented as:

Given a set of items, each with a weight and value, determine the optimal selection of items such that the weight does not pass the constraint and the total value is maximized.

Interestingly, and as you could probably guess, knapsack problems are not new type of problem, having applications in various domains like scheduling or investments. Algorithmically, these problems are tricky as past decisions heavily influence future ones in convoluted ways. However, this difficulty presents a great opportunity and use case for dynamic programming, relying on past computations to make good current decisions.

There are many subsets of knapsack problems, most of which you can investigate further below:

• 0/1 Knapsack
• Unbounded Knapsack
• Bounded Knapsack