1. (5 pts). Consider the "O-1 knapsack problem: A thief robbing a store finds n items. The ith item is worth 4 dollars and weighs wa pounds, where and we are integers. The thief wants to take as valuable a load as possible, but he can carry at most W pounds in his knapsack, for some integer W. Which items should he take, to maximize the value of the items in the knapsack? (We call this the "0-1 knapsack problem because for each item, the thief must either take it or leave it behind; he cannot take a fractional amount of an item or take an item more than once.) Show, by means of a counterexample, that the following greedy" strategy does not always determine an optimal solution: Determine the value per pound vi/w; for each item. Then sort the items by decreasing value per pound, and then add items to the knapsack in that order until you reach an item that would cause the total weight in the knapsack to exceed W pounds. (That item does not get added.) Your counterexample must assume the value of W to be 100, and must include at least 3 items, with specific values for v; and w;. In addition to these specifications, explain briefly (and clearly) how your counterexample shows the desired conclusion. Solution