Алгоритми Greedy є типом алгоритмічної стратегії, яка робить оптимальний вибір на кожному етапі з надії пошуку глобального оптимального. Вони широко використовуються в розв'язанні задач оптимізації, де локальні рішення призводять до глобально оптимального рішення. У статті досліджується концепція greedy алгоритмів, забезпечує практичні приклади, і демонструє, як виконувати пов'язані розрахунки.

Що таке Алгоритми Греді?

Узгодний алгоритм створює деталь розчину, завжди вибираючи наступний шматок, який пропонує найбільш безпосередній користі. Такий підхід простий і ефективний, але не завжди гарантує найкраще рішення для всіх проблем. Це найефективніше, коли проблема виявляє властивість greedy-choice і оптимальну підструктуру.

Практичні приклади

Загальні проблеми, які вирішуються з використанням greedy алгоритмів, включають проблему зміни монет, вибір активності та дробову задачу knapsack. Ці приклади демонструють, як зробити локально оптимальні варіанти може призвести до глобально оптимального рішення в конкретних сценаріях.

Розрахунок та реалізація

Розглянемо проблему зміни монет, де мета полягає в тому, щоб змінити певну кількість за допомогою самих кратних монет. Надаючи деномінації монети - 1, 5, 10 і 25 сантиметрів, а цільова сума становить 63 центів. Градний підхід передбачає вибір найбільшої монети менше або дорівнює рештій кількості на кожному етапі.

Розрахунок кроку:

  • Виберіть 25 центів (закінчення: 63 - 25 = 38)
  • Виберіть 25 центів (заголовок: 38 - 25 = 13)
  • Виберіть 10 центів (заголовок: 13 - 10 = 3)
  • Виберіть 1 цент (заголовок: 3 - 1 = 2)
  • Виберіть 1 цент (заголовок: 2 - 1 = 1)
  • Виберіть 1 цент (заголовок: 1 - 1 = 0)

Всього монет використовуються: 6.