Чому жадібні алгоритми не завжди працюють на прикладі Шахрая із Дори-мандрівниці.
Уявімо, що Шахрай заліз у магазин із рюкзаком, і перед ним є купа товарів, які він може вркасти. Проте ємність рюкзака не більша за 35 фунтів.
Необхідно підібрати набір товарів найбільшої вартості, які можна скласти в рюкзак. Давайте розглянемо, як працюватиме жадібний алгоритм у подібній ситуації:
Обрати найдорожчий предмет, який влізе у рюкзак.
Обрати наступний за вартістю предмет, який поміститься в рюкзаці. І тд.
У нашому прикладі найбільш дорогим товаром, який поміститься у рюкзаці виявиться магнітофон. Тепер місця ні для чого іншого не залишилось.
Шахрай вкрав товарів на $3000. Однак, якби замість магнітофону він обрав ноутбук і гітару, то вартість здобичі складала б $3500!
У цьому випадку жадібний алгоритм не дає оптимального рішення. Хоча результат не так вже і далеко від оптимуму. Для цієї задачі краще використати динамічне програмування, але про це трохи пізніше 😉 Але Шахрай, який заліз до магазину навряд чи буде прагнути ідеалу. “Достатньо гарного” рішення має вистачити.
Невеличка самоперевірка за 2 частинами.
Уявіть, що ви працюєте в фірмі з виробництва меблів і постачаєте меблі по всій країні. Коробки із меблями розміщуються у вантажівці. Всі коробки мають різний розмір, і ви стараєтесь найбільш ефективно використати доступний вам простір. Як обирати коробки для того, щоб загрузка мала найбільшу ефективність? Запропонуйте жадібний алгоритм. Чи буде таке рішення оптимальним?
Ви їдете в Європу, і у вас є 7 днів на знайомство з пам’ятками. Ви надаєте кожній пам’ятці вартість у балах ( наскільки ви хочете її побачити ) і оцінюєте тривалість поїздки. Як забезпечити максимальну вартість ( побачити все найважливіше ) під час поїдки? Запропонуйте жадібний алгоритм. Чи буде отримане рішення оптимальним?
