4. The Knapsack Problem: A famous problem in computer science is the knapsack problem. In this problem, you have a knapsack that can hold a certain weight. You have several items to choose from, each of which has a weight and value. Your goal is to pick a collection of items of maximum value, without exceeding the weight capacity. Note that you can take at most one copy of each item. For example, you might have a knapsack that can hold 10 pounds. Suppose you have the following items: The optimal solution would be to take items 2 and 3 , which together weight 9 pounds and have value 8 . You could not take items 1 and 2, however, because they weigh a combined 12 pounds and thus exceed the weight capacity. Dane Brammaj proposed the following "greedy algorithm" for the knapsack problem. For each item, determine its value-per-unit-weight by dividing its value by its weight (e.g. item 3 has a value-per-unit-weight of 5/4=1.25). Then, order the items in decreasing value-per-unit-weight. Starting from the item with the highest value-per-unit-weight, add it to the knapsack if it doesn't make the knapsack exceed its weight capacity. Go to the item with the next highest value-per-unit-weight, and add it if you can. Repeat this process until you have gone through every item. (a) Either prove that Dane Brammaj's algorithm is correct (it will always find the optimal solution) or that it is not. (b) A related problem is the fractional knapsack problem. In this case, you are allowed to take fractional parts of an item. So in the earlier example, you could now take all of item 3 and (6/7) of item 1 . This would give a total weight of 4+(6/7)7=10 and a total value of 5+(6/7)7=11. Write pseudocode generalizing Dane Brammaj's algorithm to create a greedy algorithm for fractional knapsack: you should write pseudo-code for an algorithm that is "as greedy as possible" and takes as much of the most that it can of the highest-value items. (c) Is this greedy algorithm now optimal? Justify your