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,b.b and their rspective value v,., Vn. If we pick bundle i, we gain yet now our knapsack has room for at most C-b, weights 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.7bi and we can only sell this fraction of a bundle for 0.7u. Obviously, C and all bis and v,s are positive. () (1 pts) Write the fractional knapsack problem as a linear 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, ui/bi, from the largest to the smallest, and pick them up in this order until the sack s 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 (i) (2 pts) Use LP-duality to show that there exists a threshold T such that in the optimal solution you fully take all bundles fi: & > T, and leave completely untaken any bundle fi T, and leave completely untaken any bundle fi