Greedy
Greedy Strategy based on the following principles
- choose a “progress measure”
- preprocess input accordingly
- make next decision based on what is best given current partial solution
- Main idea: Must show greedy is always no worse than any other optimal solution
- Usually can prove this by being able to transform any optimal solution into the greedy one without losing anything
Optimal Substructure
A problem has optimal substructure if any optimal solution contains optimal solutions to the subproblem