Given the following knapsack problem: item weight value 1 2 lbs $40 2 5 lbs $65 3 6 lbs $72 4 lbs $60 Knapsack capacity W=12 Find the most valuable subset of the items that fit into the knapsack. You must show and explain your intermediate steps for the following questions. a) If it is a fractional knapsack problem, provide the optimal solution using greedy algorithm (Greedy strategy: choosing items with greatest value per pound) b) If it is a 0-1 knapsack problem, provide the optimal solution using dynamic programming (you need to provide the optimal value, the list of items that make up the optimal solution, and the V table) V[k, w] = V[k - 1,w] - if wk > w [max{ V[k − 1, w], V[k − 1, w − Wk] + vk} else

Given the following knapsack problem: item weight value 1 2 lbs $40 2 5 lbs $65 3 6 lbs $72 4 lbs $60 Knapsack capacity W=12 Find the most valuable subset of the items that fit into the knapsack. You must show and explain your intermediate steps for the following questions. a) If it is a fractional knapsack problem, provide the optimal solution using greedy algorithm (Greedy strategy: choosing items with greatest value per pound) b) If it is a 0-1 knapsack problem, provide the optimal solution using dynamic programming (you need to provide the optimal value, the list of items that make up the optimal solution, and the V table) V[k, w] = V[k - 1,w] - if wk > w [max{ V[k − 1, w], V[k − 1, w − Wk] + vk} else