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:

Figure 9.2: All possible subsets for the given...