6. (8 points) Greedy Algorithms Consider a version of the Knapsack problem in wh

Question

6. (8 points) Greedy Algorithms 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) ( 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.

Explanation / Answer

Solution:

a)

In the given case we should be selecting the item which is highest in profit because the weight of all the items is same

so the items which will be selected is

72 52 41 36 31

Total Profit = 72+52+41+36+31 = 232

b)

The algorithm is given below:

we have two algorithms with different efficiencies,

Algorithm 1:

The above algorithm will take O(n log n) time to sort the array and after that O(W), time to put the items in the knapsack

W is the weight or the capacity of the knapsack

Algorithm 2:

The above algorithm will take O(WN) time to solve

where N is number of items in the itemset and W is the capacity of the knapsack.

c)
The algorithm is correct since it is always selecting the item with the highest profit to put into the knapsack.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.