Algorytm zachłanny: Różnice pomiędzy wersjami

Usunięte 3 bajty ,  10 lat temu
(Dodane informacje o miejscach w których algorytmy zachłanne mają zastosowanie.)
Algorytm zachłanny buduje zadanie dodając do zbioru ''R'' (najczęściej pustego na początku) elementy z ''C'', tj. wybiera z ''C'' element, powiedzmy ''c'', i sprawdza czy według lokalnego (zachłannego) kryterium optymalności <math>R\cup c</math> jest optymalnym rozwiązaniem. W obu przypadkach element ''c'' jest usuwany ze zbioru ''C''.
 
Istnieje wiele problemów, dla których udowodnić można, że rozwiązanie zachłanne, jest zawsze [[rozwiązanie optymalne|optymalne]] - między innymi [[minimalne drzewo rozpinające|znajdowanie minimalnego drzewa rozpinającego]], czy znajdowanie najkrótszej ścieżki [[Algorytm Dijkstry|między dwoma punktami w grafie]]. W przypadku innych problemów zachłanność może opłacać się jedynie w szczególnych przypadkach.
 
===Problem wydawania reszty===
{{main|Problem wydawania reszty}}
Algorytm wydawania reszty w przypadku niektórych zestawów monet jest rozwiązywalny na sposób zachłanny --- między innymi w przypadku systemów europejskich (1/2/5 € lub zł), lub systemu amerykańskiego. W innych przypadkach jednak algorytm się nie sprawdzi.
 
Przykładowo, dane są dwa rodzaje monet: ''2'' zł i ''5'' zł. Należy obliczyć ile, i jakich monet należy wydać, by reszta wynosiła ''6'' zł.
Anonimowy użytkownik