Given $n$ items, choose a subset to put into the knapsack

such that the capacity of the knapsack is not exceeded

and the total value of the selected items is maximized

Example

Suppose that Josie Camper is going on an overnight hike.

There are four items Josie is considering taking along on the

trip. The weight of each item and the benefit Josie feels she

would obtain from each item are listed in table.

Suppose Josie's knapsack can hold up to $14$ pounds of items.

Which items should Josie put into his knapsack so that he

maximizes his benefit?