4. (10 pts.) Greedy choice Recall that in the 0-1 knapsack problem, you are given a backpack with capacity W. There are n items and the i-th item has weight w; and value vi. The goal is to pick some items with total weight at most W that maximize the total value. More formally, you need to find an assignment (*...) with x; (0.1) (ie.. .; is either 0 or 1), where x; = 1 means the i-th item is picked and x; = 0 otherwise. The goal is to maximize E%* subject to the constraint E. SW. As we have discussed in the class, this 0-1 knapsack problem does not have the greedy choice property. Now consider the fractional knapsack problem, where you can take a fraction of an item. More formally, you need to find an assignment (1...) with x 10,11(. can be any real number inclusively between 0 and 1). The goal is to maximize subject to the constraint EXW, SW. The greedy heuristic for each step is to find the item with the largest value per pound and take as much of it as possible. Suppose the j-th item has the largest value-per-pound. Prove that there exists an optimal solution that contains as much of the j-th item as possible. (This shows the greedy choice property.)