Elements of Greedy Strategy

Posted By on September 19, 2014


Download PDF
Greedy Algorithm
Kruskal`s Algorithm

Optimal Substructure:

An optimal solution to the  problem contains within it optimal solutions to sub-problems. A’ = A – {1} (greedy choice) A’ can be solved again with the greedy algorithm. S’ = { i Î S, si ³  fi }

When do you use DP versus a greedy approach? Which should be faster?

The 0 – 1 knapsack problem:

A thief has a knapsack that holds at most W pounds. Item i : ( vi, wi ) ( v = value, w = weight ) thief must  choose items to maximize the value stolen and still fit into the knapsack. Each item must be taken or left ( 0 – 1 ).

Fractional knapsack problem:

takes parts, as well as wholes

Both the 0 – 1 and fractional problems have the optimal substructure property: Fractional:  vi / wi is the value per pound. Clearly you take as much of the item with the greatest value per pound. This continues until you fill the knapsack. Optimal (Greedy) algorithm takes O ( n lg n ), as we must sort on vi / wi = di.

Consider the same strategy for the 0 – 1 problem:

W = 50 lbs. (maximum knapsack capacity)

w1 = 10 v1 = 60 d1.= 6
w2 = 20 v2 = 100 d2.= 5
w3 = 30 v3 = 120 d3 = 4

were d is the value densityGreedy approach: Take all of 1, and all of 2: v1+ v2 = 160, optimal solution is to take all of 2 and 3:  v2 + v3= 220, other solution is to take all of 1 and 3 v1+ v3 = 180. All below 50 lbs.

When solving the 0 – 1 knapsack problem, empty space lowers the effective d of the load. Thus each time an item is chosen for inclusion we must consider both

  • i included
  • i excluded

These are clearly overlapping sub-problems for different i’s and so best solved by DP!

 

Greedy Algorithm
Kruskal`s Algorithm

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com