Вступ

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

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

Як працюють жадібні алгоритми

Жадібний алгоритм виконує наступні кроки:

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

Коли використовувати жадібні алгоритми

Жадібні алгоритми найкраще працюють, коли:

• Проблема має властивість жадібного вибору (вибір локального оптимуму призводить до глобального оптимуму).
• Проблема має оптимальну підструктуру (оптимальне рішення можна побудувати з оптимальних рішень підзадач).

Розглянемо кілька реальних проблем і як ми можемо вирішити їх за допомогою жадібних алгоритмів в Java.

Приклад 1: Проблема розмінювання монет

Задача: Мається набір номіналів монет і сума. Потрібно знайти мінімальну кількість монет, необхідних для того, щоб зробити суму.

Реалізація в Java:

import java.util.Arrays;  

public class CoinChangeGreedy {  
 public static void makeChange(int[] coins, int amount) {  
 Arrays.sort(coins); // Сортуємо монети, щоб спочатку вибрати найбільші  
 int count = 0;  
 System.out.print("Використані монети: ");  

 for (int i = coins.length - 1; i >= 0; i--) {  
 while (amount >= coins[i]) {  
 amount -= coins[i];  
 System.out.print(coins[i] + " ");  
 count++;  
 }  
 }  

 System.out.println("\nЗагальна кількість монет: " + count);  
 }  

 public static void main(String[] args) {  
 int[] coins = {1, 5, 10, 25, 50};  
 int amount = 87;  
 makeChange(coins, amount);  
 }  
}

Пояснення:

• Алгоритм завжди вибирає найбільший доступний номінал монети.
• Він віднімає вибрану монету від суми, поки сума не стане нульовою.
• Це добре працює, коли номінали монет стандартні (наприклад, валюта США), але може не працювати оптимально для довільних номіналів.

Приклад 2: Проблема вибору активностей

Задача: Мається список активностей з часом початку і закінчення. Потрібно знайти максимальну кількість активностей, які можна запланувати без накладок.

Реалізація в Java:

import java.util.Arrays;  
import java.util.Comparator;  

class Activity {  
 int start, end;  
 Activity(int start, int end) {  
 this.start = start;  
 this.end = end;  
 }  
}  

public class ActivitySelection {  
 public static void selectActivities(Activity[] activities) {  
 Arrays.sort(activities, Comparator.comparingInt(a -> a.end));  
 System.out.println("Обрані активності:");  

 int lastEndTime = 0;  
 for (Activity activity : activities) {  
 if (activity.start >= lastEndTime) {  
 System.out.println("Початок: " + activity.start + ", Кінець: " + activity.end);  
 lastEndTime = activity.end;  
 }  
 }  
 }  

 public static void main(String[] args) {  
 Activity[] activities = {new Activity(1, 3), new Activity(2, 5), new Activity(3, 9), new Activity(6, 8)};  
 selectActivities(activities);  
 }  
}

Пояснення:

• Алгоритм сортує активності за часом їх завершення.
• Він вибирає активності, що починаються після завершення останньої вибраної активності.
• Це забезпечує максимальну кількість запланованих активностей.

Висновок

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

Коли використовувати жадібні алгоритми:

✔ Коли сортування за певною властивістю призводить до оптимального рішення.
✔ Коли локально оптимальний вибір на кожному етапі гарантує глобальний оптимум.

Коли не використовувати жадібні алгоритми:

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

Розуміючи, як і коли застосовувати жадібні алгоритми, ви зможете ефективно вирішувати багато задач і покращити свої навички вирішення проблем у Java.

Щасливого кодування! 🚀

Перекладено з: Greedy Algorithms in Java: A Simple Guide with Real-World Examples