Greedy algorithm
Strategi: gör det lokalt bästa valet i varje steg och hoppas att resultatet blir globalt optimalt. Inte alltid det — men ofta nog att tillämpas.
Funkar när problemet har greedy choice property (lokalt optimum leder till globalt) + optimal substruktur. Klassiska exempel: Dijkstras (greedy + DP), Kruskals MST, Prims MST, Huffman coding, activity selection.
Vinst när det funkar: snabbt (O(n log n) typiskt), enkelt att implementera. Trap: problem som ser greedy ut men inte är (knapsack, partition). Konkurrent: DP (när greedy inte funkar), backtracking.