Consider a version of the Knapsack problem in which every item has the same weight (say...

 

Transcribed Image Text:

Consider a version of the Knapsack problem in which every item has the same weight (say the weight is 1). In this case the problem is simpler and we can use a greedy algorithm to solve the problem. a) (1 point) Consider the following instance of the Knapsack problem where every item has weight 1. We will assume the capacity of our knapsack is 5. Which items should we select if we want to maximize the total value given this input set of the values of each item? V = {15,36,22,52,31,15,72,24,26,41} b) (2 points) Describe a Greedy Algorithm that will solve this special case of the Knapsack problem. c) (5 points) Prove your algorithm is correct. Consider a version of the Knapsack problem in which every item has the same weight (say the weight is 1). In this case the problem is simpler and we can use a greedy algorithm to solve the problem. a) (1 point) Consider the following instance of the Knapsack problem where every item has weight 1. We will assume the capacity of our knapsack is 5. Which items should we select if we want to maximize the total value given this input set of the values of each item? V = {15,36,22,52,31,15,72,24,26,41} b) (2 points) Describe a Greedy Algorithm that will solve this special case of the Knapsack problem. c) (5 points) Prove your algorithm is correct.