Knapsack Problem (35) 1. Consider a collection of K items out of which n items cannot be subdivided (0-1 knapsack) and m items can be divided into fractions (fractional knapsack), K-n+m. For each item, we are given the weight in pounds and the total cost. Given a maximum weight limit V design an algorithm that selects the set of elements that will give the maximum value. Note that the problem is a combination of 0-1 and fractional knapsack problem Id |Weight (in Pounds) Cost (in Dollars) Type 50 25 60 15 40 30 50 30 50 10 3 2 9 10 (a) Give the pseudocode of your algorithm (5) (b) Show how the algorithm works, step by step, for the given example in Table 1. W (whole) indicates for the items that cannot be subdivided and F (fractional) stands for items whose fractional value can be taken (10) (c) Prove the correctness of your algorithm (10) (d) Compute the complexity of your algorithm (5 (e) Let the weight of all the items be W and the cost of all the items be C. Let n-m-K/2. Let the limit of the weight be V- K/2W. Prove that in this case, taking any subset of half the items will provide the maximum value (5) Knapsack Problem (35) 1. Consider a collection of K items out of which n items cannot be subdivided (0-1 knapsack) and m items can be divided into fractions (fractional knapsack), K-n+m. For each item, we are given the weight in pounds and the total cost. Given a maximum weight limit V design an algorithm that selects the set of elements that will give the maximum value. Note that the problem is a combination of 0-1 and fractional knapsack problem Id |Weight (in Pounds) Cost (in Dollars) Type 50 25 60 15 40 30 50 30 50 10 3 2 9 10 (a) Give the pseudocode of your algorithm (5) (b) Show how the algorithm works, step by step, for the given example in Table 1. W (whole) indicates for the items that cannot be subdivided and F (fractional) stands for items whose fractional value can be taken (10) (c) Prove the correctness of your algorithm (10) (d) Compute the complexity of your algorithm (5 (e) Let the weight of all the items be W and the cost of all the items be C. Let n-m-K/2. Let the limit of the weight be V- K/2W. Prove that in this case, taking any subset of half the items will provide the maximum value