Problem 4. (3 pts) The fractional knapsack problem: In the fractional knapsack problem we have broken into a spice store with a knapsack of capacity Ckgs (load it with more than Ckgs and it will tear up); where we aim to take a many of the n spice bundles in the store, with their respective weights bi, b2, ..., bn and their respective value vi, ..., Vn. If we pick bundle i, we gain v; yct now our knapsack has room for at most C - bi wcights before it tears. Luckily, this is a spice shop, so we can pick a fraction of a bundle as well. For example. if we pick 70% of bundle i, the weight of our knapsack increases by 0.7b; and we can only sell this fraction of a bundle for 0.7vi. Obviously, C and all bis and vis are positive. (i) (1 pts) Write the fractional knapsack problem as a lincar program, and write its dual. Your variables should correspond to the fraction of bundle i you take. The fractional knapsack problem has a nice greedy algorithm for it: sort the bundles by value-per- gram, vi/bi, from the largest to the smallest, and pick them up in this order until the sack is full. (Pick the full bundle if there's room in the knapsack, or just the fraction you can put in the knapsack without exceeding the capacity C.) You will now prove that the greedy algorithm is indeed correct using LP-duality. () (2 pts) Usc LP-duality to show that there cxists a threshold T, such that in the optimal solution you fully take all bundles {i : > n, and leave completely untaken any bundle {i : n, and leave completely untaken any bundle {i :