Пригадайте випадки, коли вам доводилося з множини можливих варіантів вибирати той, який є найкращим у даний момент, не хвилюючись про те, що цей варіант може не призвести до найкращого результату після завершення всього процесу.

Жадібні алгоритми — це загальна назва методів розв’язування задач оптимізації, при яких на кожному етапі приймається локально оптимальне рішення.

Жадібний алгоритм — це метод розв’язування оптимізаційних задач, заснований на тому, що процес прийняття рішення можна розбити на елементарні кроки, на кожному з яких приймається окреме рішення.

Ці алгоритми застосовують до тих задач, які можна розбити на окремі прості підзадачі аналогічно тому, як це робиться в алгоритмах динамічного програмування. У жадібних алгоритмах на кожному етапі з множини можливих варіантів вибирається той, який є найкращим у даний момент, із надією, що саме він забезпечить оптимальне розв’язання всієї задачі. Вибір варіанта на кожному етапі повинен відповідати таким вимогам: бути допустимим (відповідати обмеженням задачі); бути оптимальним (найкращим із усіх можливих на даному етапі); бути остаточним (не можна змінити цей вибір на наступних етапах).

Пояснимо сутність жадібних алгоритмів на прикладі 1.

Приклад 1. Банкомат може видавати купюри номіналом 500, 200, 100, 50 і 20 грн. Якими купюрами і в якій кількості повинен видати банкомат суму 2 340 грн, щоб кількість купюр була мінімальною? Відповідно до методу жадібних алгоритмів програма обслуговування банкомата на кожному кроці повинна вибирати купюри максимального номіналу з числа тих, які можна вибрати, щоб їх загальна кількістьбула мінімальною. Для цієї суми спочатку слід вибрати чотири купюри номіналом 500 грн, потім одну купюру номіналом 200 грн, далі одну купюру номіналом 100 грн. і, нарешті, дві купюри номіналом 20 грн. Усього 8 купюр.

Реалізуйте цей алгоритм.

Наведемо тепер приклад 2, який підтверджує, що жадібні алгоритми не завжди забезпечують оптимальне розв’язання задачі в цілому.

Приклад 2. Борошно міститься в контейнерах масою 110, 50 і 10 кг. Виберемо мінімальну кількість контейнерів загальною масою 150 кг. Логічно звяти 3 контейнери масою 50 кг. За жадібним алгоритмом спочатку потрібно взяти контейнер максимальної маси (110 кг), на наступних етапах — 4 контейнери масою 10 кг, тобто 5 контейнерів.

Розв'язати цю задачу, використовуючи Жадібний алгоритм.

Приклад 3. Визначте, як сплатити суму 91 грн купюрами номіналом 1, 2, 5, 10, 25 і 50 грн так, щоб загальна кількість купюр була мінімальною.

Розв'язати цю задачу, використовуючи Жадібний алгоритм.

Розглянемо задачу про пакування рюкзака. Існують різні інтерпретації цієї задачі, але її загальна сутність одна. Є декілька типів об’єктів і рюкзак, у який можна покласти певну кількість об’єктів одного або різних типів. Відома маса і ціна кожного типу об’єктів. Необхідно покласти в рюкзак такі типи об’єктів певної кількості, щоб їх маса не перевищувала допустиму масу рюкзака, а ціна об’єктів була максимальною.

1. Пакування речей

Степан збирає речі у відпустку. З собою в літак він може взяти ручну поклажу і багаж. Для ручної поклажі у нього є рюкзак, а для багажу - здоровенна валіза.

За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Степан готовий доплатити). Зрозуміло, найбільш цінні речі - ноутбук, фотоапарат, документи тощо - Степан хоче покласти в ручну поклажу.

Степан розклав усі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Він діє в такий спосіб - бере найцінніший предмет, і якщо його маса не перевищує S, то кладе його в рюкзак, інакше кладе його до валізи. Потім він бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевищує S, то кладе його в рюкзак, інакше до валізи, і таким же чином процес триває для всіх предметів в порядку спадання їх цінності.

Визначте вагу рюкзака і валізи після того, як Степан складе всі речі.

Розв'язання

В цій задачі реалізовуємо принцип, даний в умові: беремо предмет, і якщо його маса не перевищує максимально дозволену масу, то кладемо його в рюкзак, інакше кладемо його до валізи.

Нехай k1 - вага рюкзака,  k2 - вага валізи. Беремо перший предмет масою а і перевіряємо: якщо k1+а не перевищує S, то збільшуємо k1 на а , інакше  k2  збільшуємо на а.

Алгоритм розв'язання задачі:

• ввести значення S та n, змінним k1 та k2 присвоїти значення 0;

• за допомогою циклу та команди розгалуження обчислити значення  k1 та k2;

• вивести результат.

Приклад 4. Одним із найпростіших алгоритмів для розв’язування цієї задачі є жадібний алгоритм. Використаємо ідентифікатори для таких початкових даних: 

• n — кількість об’єктів, які можна покласти в рюкзак; 

• gruz — допустима маса рюкзака; 

• nazva — список типів об’єктів, які можна покласти в рюкзак; 

• zina — список цін об’єктів; 

• vaga — список ваги об’єктів.

Будемо вважати, що в наявності є об’єкти, з яких можна покласти в рюкзак рівно таку вагу, на яку розрахований рюкзак. Крім перелічених, використаємо в алгоритмі такі ідентифікатори:

• zina_1 — список цін одиниць об’єктів (наприклад, одного кг);

• kilkist — список кількостей об’єктів кожного типу, покладених у рюкзак;

• Masa — поточне значення маси об’єктів у рюкзаку;

• Sum — ціна об’єктів, покладених у рюкзак.

Існують різні підходи до розроблення алгоритмів упакування рюкзака. Будемо дотримуватися такого.