Greedy algorithms

Greedy: take locally optimal solution (which is often globally optimal, but not always)

Make change:

• Problem: coins with certain values, have to get to a given amount
• Solution: take as many as possible, starting at the highest values and decreasing until value is reached

Activity selection

Fractional knapsack

Huffman codes