Nederlands
Menu

Wat is Gretig algoritme (greedy algorithm)?

Ontwerpmethode voor algoritmen die een oplossing opbouwt door telkens de keuze te nemen die op dat moment het beste lijkt, zonder eerdere keuzes te herzien. Ze is snel en eenvoudig, maar geeft alleen een optimale oplossing als het probleem bijzondere eigenschappen heeft, zoals bij muntstelsels als het Japanse of bij het algoritme van Kruskal voor minimale opspannende bomen.

Japanse benaming: 貪欲法

“Gretig algoritme (greedy algorithm)” komt voor in 2 oefenvragen uit 1 onderwerpen, bijv. Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Gretig algoritme (greedy algorithm)

Je betaalt 8 yen met munten van 1 yen, 4 yen en 6 yen. Welke uitspraak over het aantal munten dat een gretig algoritme kiest (dat eerst zoveel mogelijk van de grootste munt gebruikt), vergeleken met het minimale aantal munten, is juist?

  1. AOok het gretige algoritme bereikt het minimum van 2 munten
  2. BHet gretige algoritme gebruikt 3 munten en mist het minimum van 2
  3. CHet gretige algoritme gebruikt 3 munten, en dat is het minimum
Antwoord en toelichting tonen

Antwoord: B. Het gretige algoritme gebruikt 3 munten en mist het minimum van 2

Het gretige algoritme neemt eerst één munt van 6 yen en betaalt de resterende 2 yen met twee munten van 1 yen: 3 munten. Maar twee munten van 4 yen betalen het bedrag met slechts 2. Omdat een gretig algoritme alleen telkens de keuze opstapelt die op dat moment het beste lijkt, is het voor sommige muntstelsels niet optimaal. Dynamisch programmeren, dat een tabel vult met het minimale aantal munten voor elk bedrag van 0 tot 8 yen, van klein naar groot, vindt altijd het minimum. Voor muntstelsels zoals de Japanse munten van 1, 5, 10, 50, 100 en 500 yen geeft het gretige algoritme altijd het minimum.

“Gretig algoritme (greedy algorithm)” in de toelichting

Vragen met “Gretig algoritme (greedy algorithm)” (2)

  1. Je betaalt 8 yen met munten van 1 yen, 4 yen en 6 yen. Welke uitspraak over het aantal munten dat een gretig algoritme kiest (dat eerst zoveel mogelijk van de grootste munt gebruikt), vergeleken met het minimale aantal munten, is juist?
  2. Een knapzak met capaciteit 8 wordt gevuld met voorwerpen gekozen uit vier voorwerpen met (gewicht, waarde) (2, 3), (3, 4), (4, 5) en (5, 6). Van elk voorwerp is er maar één, en voorwerpen kunnen niet worden gesplitst. Wat is de maximale totale waarde bij een totaal gewicht van hoogstens 8?

Verwante termen

Dynamisch programmeren (dynamic programming) Algoritme van Dijkstra Binair zoeken (binary search) Binaire heap (binary heap) Binaire zoekboom (binary search tree) Breedte-eerst zoeken (breadth-first search) Diepte-eerst zoeken (depth-first search) Gelinkte lijst (linked list) Hashtabel (hash table) Recursie

Naar de woordenlijst