Жадібний алгоритм для «Рюкзака»
Жадібний алгоритм задачі про рюкзак з гарантованою точністю 2 .
Як ми вже зазначали, жадібні евристики є найпростішими та найпопулярнішими методами вирішення різних обчислювально важких завдань. Подивимося, що ця евристика може дати для завдання про рюкзак.
Розглянемо таке завдання.
Завдання 13. Рюкзак (Knapsack)»
c 1; : : : ; c n , c j 2 N - «Вартості» предметів;
a 1; : : : ; a n , a j 2 N - "розміри" або "ваги";
B 2 N - "Розмір рюкзака".
Знайти максимальне значення f цільової функції
з обмеженням на розмір «рюкзака»:
a i x i B; x i 2 f 0; 1 g:
2.1. АЛГОРИТМИ З ОЦІНКАМИ ТОЧНОСТІ
Змістовне завдання означає вибір предметів із найбільшою сумарною вартістю, що вміщуються у рюкзак заданого розміру. Це завдання часто виникає при виборі оптимального управління у різних галузях (розподіл бюджету відділу за проектами тощо).
Розглянемо, якого результату можна досягти, використовуючи, як у розділі 2.1.1, «жадібний підхід». Перша ідея, яка зазвичай виникає при знайомстві з цим завданням, це вибирати предмети
спадання їх відносної вартості, поміщаючи в рюкзак все, що міститься (див. алгоритм 18). На жаль, про якість евристики алгоритму нічого хорошого стверджувати не можна.
Вправа 2.1.10. Доведіть, що для будь-якого числа k можна представити вхідний набір даних, для яких алгоритм 18 вибере набір, який у k разів гірший від оптимального.
Зрозуміло, що проблема полягає в тому, що «втішивши» перший невеликий, але «відносно дорогий» предмет, алгоритм ризикує пропустити великий і цінний предмет з оптимального набору.
Виявляється, гарантована якість роботицієї евристики можна покращити, якщо після закінчення її роботи порівняти вартість отриманого допустимого рішення з максимальним коефіцієнтом c max і відповідно до максимуму вибрати або «жадібне рішення», або один предмет з максимальною вартістю (ми вважаємо, що розміри всіх предметів не перевищують розмір рюкзака — інакше їх можна виключити з розгляду).
Вийде так званий модифікований жадібний алгоритм (див. алгоритм 19 ний), для якого вже можна гарантувати якість знайденого рішення.
Теорема 4. Для значення рішення f G отриманого модифікованим жадібним алгоритмом 19 «Рюк-і оптимального значення f для задачі 13 «Knapsack» виконується