## The Knapsack Problem

Now, let's reconsider the knapsack problem we looked at in *Chapter 5*, *Greedy Algorithms*, which we could describe as the subset sum problem's "big brother." It asks the following:

*"Given a knapsack of limited capacity and a collection of weighted items of different values, what set of items can be contained within the knapsack that produces the greatest combined value without exceeding the capacity?"*

This problem is also a characteristic example of *NP*-completeness, and as such, it shares many close ties to the other problems in this class.

Consider the following example:

Capacity —> 10

Number of items —> 5

Weights —> { 2, 3, 1, 4, 6 }

Values —> { 4, 2, 7, 3, 9 }

With this data, we can produce the following subsets: