For the following, design an algorithm using a greedy heuristic. Justify your \"
ID: 3770009 • Letter: F
Question
For the following, design an algorithm using a greedy heuristic. Justify your "value" function for making decisions (Why is it reasonable or natural?) If your algorithm will produce an optimal answer, give a reason (need not be rigorous) and if not, explain why with a counterexample. What is the time complexity for each cases?
A) You have an unlimited number of knapsacks, all of capacity 1, and a collection of objects of various weights, all weights being less than 1. You want an algorithm to put objects into knapsacks so as to minimize the total number of knapsacks used.
Explanation / Answer
Greedy algorithm:
First Step: Sort the objects of the collection in ascending order according to their weights.
Second Step: Take a knapsack and Start from the left most object of sorted collection.
If there room to add this object to knapsack then place it in the knapsack and move on to next object in the collection.
If there is no room then put this knapsack a side and take a new knapsack and insert the object into this new knapsack.
Time complexity:
First step:Sorting takes O(nlogn).
Second step: It takes O(n).
So overall time complexity is O(nlogn).
Counter example:
Consider the following 10 weights.
Suppose the weights of objects are
0.2 0.8
0.2 0.8
0.2 0.8
0.2 0.8
0.2 0.8
If we use greedy then first we place all 0.2 objects in one knapsack and then remaining 0.8 objects in 5 other knapsacks. Then total knapsacks required=6.
But there exist a combination in which they can be place in 5 knapsacks.
i.e 0.2,0.8 i each of the five knapsacks.
Therefore greedy algorithm doesn't give the optimal solution.