Greedy-algoritmen
Wat Maakt een Algoritme Greedy?
Een greedy algoritme bouwt stap voor stap een oplossing op, waarbij het altijd de optie kiest die er op dit moment het beste uitziet - zonder eerdere keuzes te heroverwegen. Geen backtracking, geen vooruitkijken.
Het werkt als twee eigenschappen gelden:
- Greedy choice property - een lokaal optimale keuze leidt tot een globaal optimale oplossing.
- Optimale substructuur - het resterende probleem na elke keuze is een kleinere versie van hetzelfde probleem.
Activiteitenselectie - Het Klassieke Voorbeeld
Gegeven een verzameling activiteiten met begin- en eindtijden: selecteer het maximale aantal niet-overlappende activiteiten.
Greedy strategie: sorteer op eindtijd, kies altijd de activiteit die het eerst eindigt.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
Waarom werkt dit? De activiteit kiezen die het eerst eindigt, laat de meeste ruimte voor toekomstige activiteiten. Geen andere keuze kan beter zijn.
Huffman-codering - Concept
Bouw een optimale prefixvrije binaire code door herhaaldelijk de twee laagste-frequentie symbolen samen te voegen. Dit is greedy: bij elke stap voeg je het goedkoopste paar samen. Het resultaat is een boom waarin frequente symbolen korte codes krijgen.
Jump Game
Gegeven een array waarbij nums[i] de maximale spronglengte is vanaf index i: bepaal of je de laatste index kunt bereiken.
Greedy aanpak: houd de verst bereikbare index bij. Scan van links naar rechts - als je ooit achterraakt, return false.
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
Discussion
Sign in to join the discussion