Алгоритми та структури даних · Middle · Запитання 43 з 75
Чому жадібний алгоритм може помилитися при розміні суми 6 монетами [1, 3, 4]?
- ✓Правильна відповідь: Жадібний бере 4 + 1 + 1 (три монети), а 3 + 3 - лише дві
- 2Жадібний не впорається із сумою, більшою за найбільшу монету
- 3Жадібний завжди помиляється, коли монети не є степенями двійки
Пояснення
Брати найбільшу монету першою оптимально для стандартних валют, але не для довільних наборів монет. Динамічне програмування по сумах (dp[a] = 1 + min dp[a - coin]) завжди знаходить мінімум.