Алгоритм Рюкзака - Жадібний алгоритм для задачі про рюкзак
Жадібний алгоритм для задачі про рюкзак полягає в наступному (вважаємо, що всі предмети поміщаються в рюкзак): - Вибрати максимально дорогий предмет, вартості Cmax. - Упорядкувати предмети за «питомою вартістю» (вартості поділеної на вагу), і набивати рюкзак найбільш «питомо-дорогими» предметами, доки вони влазять.
Нехай вартість цього рішення Cgreedy залежно від того, що більше, Cmax або Cgreedy, вибрати перше або друге рішення. Цей алгоритм має складність O(n log(n)), і гарантує перебування рішення, не гірше ніж удвічі від оптимального.
Для багатьох оптимізаційних завдань є простіші та швидші алгоритми, ніж динамічне програмування. До таких алгоритмів належать жадібні алгоритми. Жадібний алгоритм на кожному кроці робить локально оптимальний вибір для того, що підсумкове рішення також буде оптимальним. Не завжди виправдано, але багатьох завдань жадібні алгоритми справді дають оптимум.
Принцип жадібного вибору
Говорять, що до оптимізаційної задачі застосуємо принцип жадібного вибору (greedy choice property), якщо послідовність локально оптимальних (жадібних) виборів дає глобально оптимальне рішення. Відмінність між жадібними алгоритмами і динамічним програмуванням можна пояснити так: на кожному кроці жадібний алгоритм бере "найжирніший шматок", а потім уже намагається зробити найкращий вибір серед варіантів, які б вони не були. Алгоритм динамічного програмування приймає рішення, прорахувавши заздалегідь наслідок всіх варіантів.
Оптимальність для підзадач
Завдання, що вирішуються за допомогою жадібних алгоритмів, мають властивість оптимальності для підзадач: оптимальне рішення всього завдання містить оптимальне рішення підзадач.
І жадібні алгоритми, і динамічне програмування ґрунтуються на властивості оптимальності для підзавдань, тому може виникнути бажання застосувати жадібний алгоритм замість динамічного, і навпаки. В одному випадку це може не дати оптимального рішення, у другому може призвести до менш ефективного рішення.
Прикладом може бути завдання про рюкзак - вона полягає в тому, щоб укласти в рюкзак речі таким чином, щоб їх сумарна вага не перевищувала граничного значення W і сумарна вартість речей була максимальна. Завдання має два різновиди – безперервне завдання та дискретне. Наприклад, речі неподільні (золотий злиток) та ділимо (золотий пісок).
Нехай є n речей, кожна з яких має вартість v i і вага w i.
Стратегія жадібного алгоритму полягає в наступному: розраховується питома ціна речі c i = v i / w i.
Речі сортуються у порядку зменшення питомої ціни. Першою вибирається річ з максимальною питомою ціною, потім з безлічі, що залишилася, знову вибирається річ з максимальною ціною і т.д. При цьому умовою вибору є те, що річ, що додається, не призводить до перевищення граничної ваги W.
У разі безперервного завдання про рюкзак виходить загальне оптимальне рішення, у разі дискретного – ні.