Algorytmy i struktury danych · Middle · Pytanie 43 z 75
Dlaczego algorytm zachłanny może zawieść przy wydawaniu 6 monetami [1, 3, 4]?
- ✓Poprawna odpowiedź: Zachłanny bierze 4 + 1 + 1 (trzy monety), a 3 + 3 to tylko dwie
- 2Zachłanny nie radzi sobie z kwotą większą od największej monety
- 3Zachłanny zawsze zawodzi, gdy monety nie są potęgami dwójki
Wyjaśnienie
Branie największej monety najpierw jest optymalne dla standardowych walut, ale nie dla dowolnych zestawów monet. Programowanie dynamiczne po kwotach (dp[a] = 1 + min dp[a - coin]) zawsze znajduje minimum.