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

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

Проблема в том, что иногда этот подход срабатывает, а иногда нет.

Чтобы не погружаться в скучную теорию, давайте сразу посмотрим на несколько задач, которые можно решить с помощью жадных алгоритмов. Начнём с задачи о выборе задач, с которой обычно не возникает никаких проблем.

👉 Важное уточнение: статья описывает только основы и простые примеры жадных алгоритмов. Теория, подробности и глубинная математика — в учебниках и на курсе «Алгоритмы и структуры данных» от 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, которое мы можем потратить.

  1. Сортируем задачи по возрастанию времени выполнения.
  2. Создаем переменные count (количество выполненных задач) и totalTime (общее затраченное время).
  3. Проходим по списку задач, добавляя время выполнения каждой задачи к totalTime.
  4. Если после добавления времени текущей задачи totalTime не превысил maxTime, увеличиваем счетчик выполненных задач count. Иначе, прерываем цикл, так как больше задач выполнить нельзя.
  5. Возвращаем количество выполненных задач count.
  6. Запускаем функцию с задачами [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, которую надо разменять. Разберём, что в ней происходит:

  1. Мы сортируем монеты в порядке убывания, чтобы начать с самых больших монет. В нашем случае это 25, затем 10, 5 и 1.
  2. Создаем переменную count, которая будет считать количество использованных монет.
  3. Идем по списку монет и для каждой монеты, пока можем, вычитаем ее номинал из суммы и увеличиваем счетчик монет count.
  4. Если в итоге сумма стала равна нулю, значит, мы успешно разменяли ее, и тогда возвращаем количество использованных монет — задача решена. Если нет, возвращаем -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 кг и следующие предметы:

  1. Предмет A: вес 7 кг, стоимость 100₽
  2. Предмет B: вес 5 кг, стоимость 80₽
  3. Предмет 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() в браузере: когда можно и когда нельзя

document.open(), write(), writeln(), close() в браузере: когда можно и когда нельзя

Эти методы управляют потоковой записью HTML прямо в документ. Они удобны во время парсинга страницы, но опасны после загрузки: могут стереть текущее содержимое, блокируют поток, ухудшают производительность и плохо сочетаются с современными практиками. Ниже — безопасные сценарии, риски и актуальные альтернативы.

Функция находится в статусе ограниченной доступности в Baseline.

Читать дальше
JS
  • 10 августа 2025
Как работает navigator.credentials: API для входа без пароля

Как работает 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.

Нашли ошибку или опечатку? Напишите нам.

JS
  • 3 августа 2025
Как использовать cause для более понятной обработки ошибок в JavaScript

Как использовать cause для более понятной обработки ошибок в JavaScript

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

Читать дальше
JS
  • 3 августа 2025
HTTP/3: зачем он нужен и как понять, что он работает

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:

  1. Откройте DevTools → вкладка Network.
  2. Перезагрузите страницу.
  3. Добавьте колонку Protocol (правый клик по шапке таблицы).
  4. Посмотрите, есть ли 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.

Нашли ошибку или опечатку? Напишите нам.

JS
  • 27 июля 2025
Как работает Map в JavaScript

Как работает 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

Отличия от объектов

ОсобенностьMapObject
Типы ключейлюбыетолько строки и символы
Порядоксохраняетсяне гарантирован
Итерацияпроще и более гибкаятребует Object.entries и т. д.
Производительностьбыстрее на больших объёмахможет быть медленнее

Когда использовать Map

Используйте Map, если:

  • Нужен предсказуемый порядок элементов.
  • Ключами должны быть не только строки.
  • Нужно часто добавлять, удалять или перебирать элементы.
  • Важно избежать конфликтов с ключами вроде __proto__ или hasOwnProperty.

Заключение

Map — мощная и удобная структура данных, особенно когда работа с обычными объектами становится громоздкой. Она расширяет привычные возможности, делает код чище и понятнее, а также даёт контроль над ключами и порядком. В современном JavaScript Map — это стандарт, на который стоит ориентироваться в сложных приложениях.

Больше обзоров веб-функций — в телеграм-канале HTML Academy.

Нашли ошибку или опечатку? Напишите нам.

JS
  • 27 июля 2025
10 приёмов работы с console, которые должен знать каждый разработчик

10 приёмов работы с console, которые должен знать каждый разработчик

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

Читать дальше
JS
  • 18 июля 2025
Оператор ** в JS: возведение в степень

Оператор ** в JS: возведение в степень

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

Читать дальше
JS
  • 25 июня 2025
Полный гайд по объекту Date в JavaScript

Полный гайд по объекту Date в JavaScript

Объект Date позволяет создавать, сравнивать и форматировать дату и время. Используется для отображения текущего времени, вычисления интервалов и работы с таймзонами в веб-приложениях.

Доступно в Baseline в статусе «Widely Available» с 2018-01-29

Читать дальше
JS
  • 25 июня 2025
FormControl и FormGroup в Angular

FormControl и FormGroup в Angular

Если вы разрабатываете веб-приложение, вам рано или поздно придётся собирать данные от пользователя. К счастью, реактивные формы в Angular позволяют делать это без лишней сложности — без нагромождения директив и с минимальным количеством шаблонного кода. Более того, их просто валидировать, так что можно обойтись даже без end-to-end тестов.

Говоря проще, form control’ы в Angular дают полный контроль разработчику — ничего не происходит автоматически, и каждое решение по вводу и управлению принимается явно и осознанно. В этом руководстве мы покажем, как объединять form control’ы в form group’ы, чтобы структурировать форму и упростить доступ к её элементам — как к логическим блокам. Чтобы лучше понять, как работают form group’ы в Angular, мы шаг за шагом соберём реактивную форму.

Для работы с примером скачайте стартовый проект с GitHub и откройте его в VS Code. Если ещё не обновляли Angular, поставьте актуальную на момент написания версию — Angular v18.

Читать дальше
JS
  • 1 июня 2025
AOT против JIT-компилятора: что лучше для разработки на Angular?

AOT против JIT-компилятора: что лучше для разработки на Angular?

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

Читать дальше
JS
  • 25 мая 2025