# Elements of Greedy Strategy

**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, s

_{i }³ f_{i}}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 : ( v

_{i}, w_{i }) ( 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: v_{i} / w_{i }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 v_{i} / w_{i }= d_{i}.

Consider the same strategy for the 0 – 1 problem:

W = 50 lbs. (maximum knapsack capacity)

w _{1 }= 10v _{1 }= 60d _{1}.= 6w _{2 }= 20v _{2 }= 100d _{2}.= 5w _{3 }= 30v _{3 }= 120d _{3 }= 4were d is the value densityGreedy approach: Take all of 1, and all of 2: v

_{1}+ v_{2 }= 160, optimal solution is to take all of 2 and 3: v_{2 }+ v_{3}= 220, other solution is to take all of 1 and 3 v_{1}+ v_{3 }= 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!