Жадные алгоритмы. Задачи о размене, рюкзаке и о задачах
- 2 мая 2023
Программистам часто приходится решать задачи оптимизации. В таких задачах мы ищем лучшее решение среди всех возможных вариантов. «Лучшее» может означать самое большое или самое маленькое. Например, найти кратчайший путь между точками на карте в навигаторе — задача оптимизации.

Жадные алгоритмы — это подход к решению задач оптимизации, в котором мы делаем лучший выбор на каждом шаге, надеясь, что это приведёт к лучшему решению в итоге. Это простые для понимания алгоритмы, которые ещё и быстро работают.
Проблема в том, что иногда этот подход срабатывает, а иногда нет.
Чтобы не погружаться в скучную теорию, давайте сразу посмотрим на несколько задач, которые можно решить с помощью жадных алгоритмов. Начнём с задачи о выборе задач, с которой обычно не возникает никаких проблем.
👉 Важное уточнение: статья описывает только основы и простые примеры жадных алгоритмов. Теория, подробности и глубинная математика — в учебниках и на курсе «Алгоритмы и структуры данных» от HTML Academy.
Задача о планировании задач
Задача: начало недели, у разработчика в бэклоге есть список задач от разных отделов, каждая из которых требует определённого времени для выполнения. Мы хотим выбрать максимальное количество задач, которые можно выполнить, учитывая ограничение по времени.
👉 Эта задача является одной из тех, где жадный алгоритм даёт оптимальное решение.

Решение: мы выбираем задачи в порядке возрастания времени выполнения и выполняем их до тех пор, пока не достигнем максимального доступного времени. Этот подход приводит к выполнению наибольшего количества задач за ограниченное время.
❗Задача не учитывает важность задач или озлобленность начальников других отделов, мы принимаем во внимание только время их выполнения. Возможно, в реальном мире весь этот код придётся переписать.
Пример кода на JavaScript:
function taskSelection(tasks, maxTime) {
tasks.sort((a, b) => a - b);
let count = 0;
let totalTime = 0;
for (let task of tasks) {
totalTime += task;
if (totalTime <= maxTime) {
count++;
} else {
break;
}
}
return count;
}
let tasks = [3, 2, 1, 4, 5];
let maxTime = 9;
console.log(taskSelection(tasks, maxTime)); // Output: 4 (1 + 2 + 3 + 3)
Функция taskSelection
принимает список времени выполнения задач tasks
и максимальное время maxTime
, которое мы можем потратить.
- Сортируем задачи по возрастанию времени выполнения.
- Создаем переменные
count
(количество выполненных задач) иtotalTime
(общее затраченное время). - Проходим по списку задач, добавляя время выполнения каждой задачи к
totalTime
. - Если после добавления времени текущей задачи
totalTime
не превысилmaxTime
, увеличиваем счетчик выполненных задачcount
. Иначе, прерываем цикл, так как больше задач выполнить нельзя. - Возвращаем количество выполненных задач
count
. - Запускаем функцию с задачами
[3, 2, 1, 4, 5]
и максимальным временем9
. Функция вернет 4, потому что мы можем выполнить задачи с временем 1, 2, 3 и еще раз 3 (первую, вторую и две третьих задачи) в рамках 9 единиц времени.
Так мы получим оптимальное решение и сможем выполнить максимальное количество задач за заданное время.
Теперь перейдём к другой популярной задаче, в которой жадные алгоритмы приводят к оптимальному результату далеко не всегда.
Задача о размене монет
Задача: у нас есть набор монет с разными номиналами, и нам нужно разменять заданную сумму минимальным количеством монет.

Решение: используем как можно больше монет с максимальным номиналом, затем переходим к меньшему номиналу и так далее. По крайней мере, так мы можем решать эту задачу в духе жадных алгоритмов.
Пример кода на JavaScript:
function coinChange(coins, amount) {
coins.sort((a, b) => b - a);
let count = 0;
for (let i = 0; i < coins.length; i++) {
while (amount >= coins[i]) {
amount -= coins[i];
count++;
}
}
if (amount === 0) {
return count;
} else {
return -1;
}
}
let coins = [1, 5, 10, 25];
let amount = 63;
console.log(coinChange(coins, amount)); // Output: 6 (25 + 25 + 10 + 1 + 1 + 1)
Функция coinChange
получает на вход список монет coins
и сумму amount
, которую надо разменять. Разберём, что в ней происходит:
- Мы сортируем монеты в порядке убывания, чтобы начать с самых больших монет. В нашем случае это 25, затем 10, 5 и 1.
- Создаем переменную
count
, которая будет считать количество использованных монет. - Идем по списку монет и для каждой монеты, пока можем, вычитаем ее номинал из суммы и увеличиваем счетчик монет
count
. - Если в итоге сумма стала равна нулю, значит, мы успешно разменяли ее, и тогда возвращаем количество использованных монет — задача решена. Если нет, возвращаем
-1
, потому что разменять оставшуюся сумму с такими монетами нельзя.
В итоге для набора монет [1, 5, 10, 25]
и суммы 63
функция вернёт число 6
, потому что нам потребуется 6 монет для размена: две по 25, одна по 10 и три по 1.
❌ Когда жадный алгоритм не сработает
Пусть у нас есть следующий набор монет: [1, 4, 5]
. Теперь допустим, нам нужно разменять сумму 8
.
Если мы применим жадный алгоритм к этому набору монет, он сначала выберет монету с номиналом 5
, так как она имеет наибольший номинал. Затем, чтобы разменять оставшуюся сумму 3
, алгоритм выберет три монеты по 1
. В итоге, жадный алгоритм использует 4 монеты: [5, 1, 1, 1]
.
Однако, оптимальное решение здесь — использовать две монеты по 4
(сумма 8
разменяется на [4, 4]
). В этом случае, жадный алгоритм не приводит к оптимальному результату.
Задача о рюкзаке
Другой пример возможной неоптимальности — задача о рюкзаке.
Задача: у нас есть рюкзак ограниченной вместимости и набор предметов с разными весами и стоимостями. Наша цель — уложить максимальную стоимость предметов в рюкзак, не превышая его вместимость.
Обычно эта задача приводится в двух вариантах — когда мы не можем «распилить» предметы на части или взять их небольшое количество («0-1 рюкзак») и когда можем («дробный» рюкзак).
☹️ Неоптимальное решение
Попытка применить жадный алгоритм к первому варианту задачи, например, выбирая предметы с наибольшим соотношением стоимости к весу, не гарантирует оптимального решения в целом.
Например, рассмотрим рюкзак вместимостью 10 кг и следующие предметы:
- Предмет A: вес 7 кг, стоимость 100₽
- Предмет B: вес 5 кг, стоимость 80₽
- Предмет C: вес 3 кг, стоимость 50₽
Если применить жадный алгоритм, выбирая предметы с наибольшим соотношением стоимости к весу, мы возьмем предмет C (стоимость/вес = 16.67), а затем предмет B (стоимость/вес = 16). В итоге у нас будет 130₽ стоимости и 8 кг веса.
Однако, оптимальное решение здесь — взять предметы A и C, что даст нам общую стоимость 150₽ и общий вес 10 кг. Так что для реализации первого варианта лучше подойдёт динамическое программирование.
😉 Оптимальное решение
Вот пример кода для оптимального решения этой задачи c помощью жадного алгоритма:
function fractionalKnapsack(items, capacity) {
// Сортировка предметов по убыванию их удельной стоимости (стоимость / вес)
items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
let totalValue = 0;
let remainingCapacity = capacity;
for (const item of items) {
if (remainingCapacity <= 0) {
break;
}
const fraction = Math.min(1, remainingCapacity / item.weight);
// Обновление общей стоимости и оставшейся вместимости рюкзака
totalValue += item.value * fraction;
remainingCapacity -= item.weight * fraction;
}
return totalValue;
}
// Пример использования функции
const items = [{
weight: 10,
value: 60
},
{
weight: 20,
value: 100
},
{
weight: 30,
value: 120
},
];
const capacity = 50;
console.log(fractionalKnapsack(items, capacity)); // Выведет 240
Функция fractionalKnapsack
принимает два аргумента: массив items
, содержащий объекты с весом и стоимостью каждого предмета, и число capacity
, представляющее вместимость рюкзака.
В целом, жадные алгоритмы — только один из подходов, который может пригодиться вам в работе, но далеко не единственный. Узнайте больше об этом на курсе «Алгоритмы и структуры данных» — лишним точно не будет.
Материалы по теме
«Доктайп» — журнал о фронтенде. Читайте, слушайте и учитесь с нами.
Читать дальше




5 книг по паттернам проектирования, которые улучшат ваш код
Каждый найдёт подходящее для себя.
- 18 апреля 2023

В чём разница между интерфейсами и типами в TypeScript
Отвечаем на популярный вопрос с собеседований.
- 14 апреля 2023

Как собрать проект на Webpack. Простой гайд для новичков
Простейший пример для тех, кому надо разобраться по работе или учёбе.
- 7 апреля 2023

XSS-уязвимости и как их избежать
Разбираемся в популярном типе атак в вебе.
- 7 апреля 2023


