Жадные алгоритмы: короткий обзор
- 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
, представляющее вместимость рюкзака.
В целом, жадные алгоритмы — только один из подходов, который может пригодиться вам в работе, но далеко не единственный. Узнайте больше об этом на курсе «Алгоритмы и структуры данных» — лишним точно не будет.
Материалы по теме
«Доктайп» — журнал о фронтенде. Читайте, слушайте и учитесь с нами.
Читать дальше

document.open(), write(), writeln(), close() в браузере: когда можно и когда нельзя
Эти методы управляют потоковой записью HTML прямо в документ. Они удобны во время парсинга страницы, но опасны после загрузки: могут стереть текущее содержимое, блокируют поток, ухудшают производительность и плохо сочетаются с современными практиками. Ниже — безопасные сценарии, риски и актуальные альтернативы.
Функция находится в статусе ограниченной доступности в Baseline.
- 10 августа 2025

Как работает navigator.credentials: API для входа без пароля
navigator.credentials
— это интерфейс Web Authentication API, который позволяет браузеру управлять учётными данными пользователя. С его помощью можно безопасно получать, сохранять и автоматически подставлять данные для входа: пароли, токены или ключи. Это делает процесс аутентификации проще и безопаснее — особенно на сайтах, где важен пользовательский опыт и скорость входа.
Доступно в Baseline в статусе «Widely Available» с 2022-07-15
Как это работает
Сегодня вам бесплатно доступен тренажёр по HTML и CSS.
Вы можете запросить сохранённые данные с помощью navigator.credentials.get()
. Например, при загрузке страницы входа можно попытаться автоматически получить логин и пароль пользователя, если он ранее их сохранил:
const cred = await navigator.credentials.get({
password: true,
mediation: 'optional' // чтобы не мешать потоку, если данных нет
});
if (cred) {
console.log('Получен логин:', cred.id);
console.log('Пароль:', cred.password);
// Здесь можно автоматически отправить данные на сервер
}
Если учётные данные доступны, вы можете использовать их для входа без дополнительных действий от пользователя. Это особенно удобно на мобильных устройствах и в приложениях с частыми сессиями.
Можно ли сохранять логин и пароль вручную?
Да, через navigator.credentials.store()
вы можете сохранить учётные данные, которые пользователь только что ввёл:
const cred = new PasswordCredential({
id: 'user@example.com',
password: '12345678'
});
await navigator.credentials.store(cred);
Теперь при следующем визите вы сможете использовать get()
, чтобы получить эти данные без необходимости ручного ввода.
Безопасность
API работает только на HTTPS и требует, чтобы страница была в фокусе. Браузеры могут показывать уведомления, если данные используются без явного действия пользователя — это защита от скрытых запросов.
Поддержка и ограничения
- Поддерживается в Chrome, Edge, Android WebView.
- Safari и Firefox поддерживают только часть API или вовсе не поддерживают.
- Нельзя использовать на сторонних сайтах (только собственный домен).
Это API особенно хорошо подходит для проектов, где важна быстрая авторизация и нет смысла постоянно спрашивать логин-пароль у пользователя.
Больше обзоров веб-функций — в телеграм-канале HTML Academy.
Нашли ошибку или опечатку? Напишите нам.
- 3 августа 2025

Как использовать cause для более понятной обработки ошибок в JavaScript
Новое свойство cause
в объекте error
позволяет узнать исходную причину сбоя и облегчить отладку, особенно при повторении ошибок. Оно помогает выстроить цепочку событий и лучше понимать, где возникла проблема. Свойство доступно в Baseline в статусе «Widely Available» с 20 марта 2024 года.
- 3 августа 2025

HTTP/3: зачем он нужен и как понять, что он работает
HTTP/3 — это новая версия протокола обмена данными между браузером и сервером. В отличие от предыдущих HTTP/1.1 и HTTP/2, он построен поверх протокола QUIC и использует UDP вместо TCP. Это делает соединения быстрее, стабильнее и безопаснее.
HTTP/3 доступен в Baseline в статусе «Newly Available» с 2024-09-16.
Чем HTTP/3 лучше
🚀 Сегодня вам бесплатно доступен тренажёр по HTML и CSS.
- Быстрее устанавливается соединение. Больше нет отдельной стадии TLS: всё объединено.
- Меньше задержек. Даже при потере пакета браузер не ждёт восстановления всего потока, как в TCP.
- Устойчивость к переключениям сети. QUIC сохраняет соединение, даже если пользователь, например, переключился с Wi-Fi на LTE.
- Безопасность по умолчанию. Все соединения — только через шифрование (TLS 1.3).
Эти преимущества особенно важны для мобильных пользователей и тех, кто часто сталкивается с нестабильным интернетом.
Как работает
HTTP/3 основан на QUIC — это транспортный протокол от Google, который работает через UDP. Он умеет передавать данные параллельно по разным потокам, не блокируя друг друга при сбоях. QUIC внедрён в современные браузеры и серверные платформы.
Нужно ли что-то делать?
Если вы разработчик сайта или веб-приложения, то скорее всего ничего специально делать не нужно — браузер сам выберет HTTP/3, если сервер его поддерживает. Ваш сайт будет работать быстрее просто потому, что инфраструктура на это перешла.
Если вы настраиваете сервер (например, NGINX или Cloudflare), тогда стоит включить поддержку HTTP/3. На популярных платформах это можно сделать одной строчкой.
Как проверить, используется ли HTTP/3
В Chrome или Edge:
- Откройте DevTools → вкладка Network.
- Перезагрузите страницу.
- Добавьте колонку Protocol (правый клик по шапке таблицы).
- Посмотрите, есть ли
h3
у запросов — это и есть HTTP/3.
Через терминал (если у вас установлен curl):
curl -I --http3 https://example.com
Если сервер не поддерживает HTTP/3, будет ошибка или произойдёт откат на HTTP/2.
Через JavaScript
На уровне кода нельзя напрямую узнать версию протокола, но можно сделать fetch и посмотреть заголовки ответа через инструменты разработчика:
fetch('https://example.com')
.then(response => console.log(response.headers))
А затем проверить в DevTools, какой протокол был использован.
Что важно помнить
- HTTP/3 — это не «фича», которую вы вызываете в коде, а часть транспортного уровня.
- Он поддерживается большинством современных браузеров: Chrome, Firefox, Edge, Safari.
- Но он работает только с HTTPS, как и HTTP/2.
Заключение
HTTP/3 делает интернет быстрее, безопаснее и стабильнее — особенно на слабых сетях и мобильных устройствах. Вам не нужно менять HTML, JavaScript или CSS, чтобы получить преимущество. Главное — чтобы сервер и хостинг поддерживали эту технологию.
Если вы разрабатываете сайт с упором на производительность — убедитесь, что HTTP/3 включён. Это шаг вперёд к более отзывчивым и доступным интерфейсам.
Больше обзоров веб-функций — в телеграм-канале HTML Academy.
Нашли ошибку или опечатку? Напишите нам.
- 27 июля 2025

Как работает Map в JavaScript
Коллекция Map
— это встроенный объект JavaScript, предназначенный для хранения пар ключ-значение. Она похожа на обычный объект ({}
), но обладает важными преимуществами:
- Любые типы ключей — строки, числа, объекты, функции.
- Сохранение порядка вставки — перебор идёт в том порядке, в котором вы добавили элементы.
- Удобные методы для работы —
set()
,get()
,has()
,delete()
,clear()
и итерации черезfor...of
.
Эта структура особенно полезна, если вы хотите чётко контролировать порядок элементов и не ограничиваться только строковыми ключами, как в обычных объектах.
Пример: создаём коллекцию и работаем с ней
? Сегодня вам бесплатно доступен тренажёр по HTML и CSS.
const userInfo = new Map();
userInfo.set('name', 'Алексей'); // строка
userInfo.set(42, 'Число'); // число
userInfo.set(true, 'Булево'); // логическое значение
console.log(userInfo.get(42)); // Выведет: 'Число'
Здесь мы добавили три элемента с разными типами ключей. Именно это отличает Map
от обычного объекта — вы можете использовать, например, ключи-объекты или даже функции:
const objKey = { id: 1 };
const fnKey = () => {};
userInfo.set(objKey, 'объект');
userInfo.set(fnKey, 'функция');
console.log(userInfo.get(objKey)); // 'объект'
Перебор Map
Вы можете пройтись по элементам Map
с помощью for...of
:
for (const [key, value] of userInfo) {
console.log(key, value);
}
Также доступны методы:
map.keys()
— только ключи,map.values()
— только значения,map.entries()
— пары [ключ, значение].
console.log([...userInfo.keys()]); // Все ключи
console.log([...userInfo.values()]); // Все значения
Проверка наличия, удаление и очистка
userInfo.has('name'); // true
userInfo.delete(42); // удаляет элемент с ключом 42
userInfo.clear(); // полностью очищает Map
Отличия от объектов
Особенность | Map | Object |
---|---|---|
Типы ключей | любые | только строки и символы |
Порядок | сохраняется | не гарантирован |
Итерация | проще и более гибкая | требует Object.entries и т. д. |
Производительность | быстрее на больших объёмах | может быть медленнее |
Когда использовать Map
Используйте Map
, если:
- Нужен предсказуемый порядок элементов.
- Ключами должны быть не только строки.
- Нужно часто добавлять, удалять или перебирать элементы.
- Важно избежать конфликтов с ключами вроде
__proto__
илиhasOwnProperty
.
Заключение
Map
— мощная и удобная структура данных, особенно когда работа с обычными объектами становится громоздкой. Она расширяет привычные возможности, делает код чище и понятнее, а также даёт контроль над ключами и порядком. В современном JavaScript Map
— это стандарт, на который стоит ориентироваться в сложных приложениях.
Больше обзоров веб-функций — в телеграм-канале HTML Academy.
Нашли ошибку или опечатку? Напишите нам.
- 27 июля 2025

10 приёмов работы с console, которые должен знать каждый разработчик
Консоль разработчика — важный инструмент отладки в JavaScript. С помощью методов console
можно выводить информацию о работе скрипта, отслеживать ошибки, логировать данные и анализировать производительность. В браузере это доступно через панель разработчика (DevTools), обычно на вкладке «Console».
- 18 июля 2025

Оператор ** в JS: возведение в степень
Оператор **
— это современный и лаконичный способ возводить числа в степень в JavaScript.
Он появился в стандарте ECMAScript 2016 и заменил собой более громоздкий вызов Math.pow()
.
Вместо Math.pow(3, 4)
теперь можно написать 3 ** 4
, что читается и набирается проще.
- 25 июня 2025

Полный гайд по объекту Date в JavaScript
Объект Date
позволяет создавать, сравнивать и форматировать дату и время. Используется для отображения текущего времени, вычисления интервалов и работы с таймзонами в веб-приложениях.
Доступно в Baseline в статусе «Widely Available» с 2018-01-29
- 25 июня 2025

FormControl и FormGroup в Angular
Если вы разрабатываете веб-приложение, вам рано или поздно придётся собирать данные от пользователя. К счастью, реактивные формы в Angular позволяют делать это без лишней сложности — без нагромождения директив и с минимальным количеством шаблонного кода. Более того, их просто валидировать, так что можно обойтись даже без end-to-end тестов.
Говоря проще, form control’ы в Angular дают полный контроль разработчику — ничего не происходит автоматически, и каждое решение по вводу и управлению принимается явно и осознанно. В этом руководстве мы покажем, как объединять form control’ы в form group’ы, чтобы структурировать форму и упростить доступ к её элементам — как к логическим блокам. Чтобы лучше понять, как работают form group’ы в Angular, мы шаг за шагом соберём реактивную форму.
Для работы с примером скачайте стартовый проект с GitHub и откройте его в VS Code. Если ещё не обновляли Angular, поставьте актуальную на момент написания версию — Angular v18.
- 1 июня 2025

AOT против JIT-компилятора: что лучше для разработки на Angular?
Angular — один из самых популярных фреймворков для фронтенда — предлагает два подхода к компиляции: предварительная компиляция и динамическая компиляция во время выполнения. Оба метода играют важную роль в оптимизации приложений на Angular и повышении их производительности. В этом материале мы рассмотрим различия между ними, их преимущества и разберёмся, когда стоит использовать каждый из подходов.
- 25 мая 2025