Elements of the 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)

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

were d is the value density

Greedy approach: Take all of 1, and all of 2: v₁+ v₂ = 160, optimal solution is to take all of 2 and 3:  v₂ + v₃= 220, other solution is to take all of 1 and 3 v₁+ v₃ = 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!