Что такое жадный алгоритм

Жадный алгоритм — это подход, где на каждом шаге выбирается локально оптимальное решение в надежде получить глобально оптимальный результат. Он не всегда даёт идеальное решение, но часто эффективен для задач, где локальные оптимумы ведут к глобальному (например, задача о рюкзаке или алгоритм Дейкстры).

Пример — задача о выборе монет для сдачи с минимальным количеством:

int[] coins = {25, 10, 5, 1}; // номиналы монет
int amount = 63;
int count = 0;

for (int coin : coins) {
    while (amount >= coin) {
        amount -= coin;
        count++;
    }
}
System.out.println("Минимальное количество монет: " + count); // 6 (25+25+10+1+1+1)