Problem 5: Fractional Knapsack Problem A thief is given the choice of n objects to steal, but only has one knapsack with a capacity of taking M weight. Each object i has weight w., and profit p, (a) First, suppose that the objects are divisible (e.g., the thief is in a cheese shop and the items are rolls of cheese that can be cut). For each object , if a fraction Ep 0 1 (taking Zi = 1 would be taking the entire object) is placed in the knapsck, then the profit earned is piai. Come up with an efficient greedy algorithm for maximizing the profit of the thief. Prove the correctness and running time. (b) Now, suppose the items cannot be taken fractionally. In other words, the thief can either take an entire item or leave it behind. Suppose we also know the following: the order of these items when sorted by increasing weight is the same as their order when sorted by decreasing value. Give a greedy algorithm to find an optimal solution to this variant of the knapsack problem. Prove the correctness and running time