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

Модули Angular для организации кода и ленивой загрузки
Модули — один из ключевых инструментов Angular для построения масштабируемых и поддерживаемых приложений. В этой статье мы подробно рассмотрим:
- что такое модули в Angular;
- зачем они нужны;
- как их использовать для структурирования кода;
- как реализовать «ленивую» загрузку модулей;
- и чем отличаются Feature, Core и Shared модули.
Если вы только начинаете изучать Angular или хотите углубить свои знания, эта статья поможет вам лучше понять, как правильно организовать архитектуру Angular-приложения.
- 12 мая 2025

Навигация в Angular: RouterLink, Router.navigate и Router.navigateByUrl
Директива RouterLink
позволяет настраивать переходы между маршрутами прямо в шаблоне Angular. А методы Router.navigate
и Router.navigateByUrl
, доступные в классе Router
, дают возможность управлять навигацией программно — прямо из кода компонентов.
Разберёмся, как работают RouterLink
, Router.navigate
и Router.navigateByUrl
.
- 11 мая 2025

Полное руководство по Lazy Loading в Angular
Если вы создаёте большое Angular-приложение, вам наверняка важно, чтобы оно загружалось быстро. Представьте, что вы устраиваете вечеринку и хотите подавать закуски не сразу, а по мере прихода гостей, чтобы не перегрузить кухню. «Ленивая» загрузка в Angular работает примерно так же: вместо того чтобы загружать всё приложение целиком сразу, вы подгружаете только те части, которые нужны — и только когда они нужны.
В этом пошаговом руководстве мы разберём, как реализовать lazy loading в Angular.
- 10 мая 2025

Все (ну или почти все) способы автоматически перезагрузить страницу раз в N секунд
Иногда страницу нужно просто перезагрузить. Полностью. Не компонент, не блок, а именно целиком. Без обсуждений, без лишней логики. Например, чтобы:
- экран с результатами обновлялся каждые 10 секунд;
- интерфейс на стенде показывал последние данные без кнопок;
- страницы в интранете не устаревали, пока никто не смотрит.
Это можно сделать в любой связке: HTML, JS, Python, PHP, Go, Node.js — не важно. Ну и если говорить совсем прямо, то совсем разных способов всего три, а остальное просто вариации.
- 5 мая 2025

Поиск с конца массива в JavaScript: findLast и findLastIndex в JavaScript
С недавних пор в JavaScript появились два полезных метода для массивов: findLast
и findLastIndex
. Они делают то же, что и привычные find
и findIndex
, только проходят массив с конца.
- 5 мая 2025

Vite 6: Новый этап в развитии фронтенд-разработки
Vite — это современный инструмент сборки, который значительно ускоряет процесс разработки фронтенда, благодаря своим невероятно быстрым и удобным функциям. И вот, наконец, вышел новый релиз Vite 6, который приносит массу улучшений и новых возможностей для разработчиков. Давайте посмотрим, что нового появилось в Vite 6 и как это может повлиять на вашу работу.
- 16 января 2025

Всё, что нужно знать о работе с API в JavaScript: пошаговый разбор
Работа с API — это основа веб-разработки. Если вы хотите получать данные с сервера, отправлять информацию или взаимодействовать с внешними сервисами (например, картами Google, платёжными системами или погодными сервисами), вам не обойтись без этого навыка. Разберём работу с API на практике: от базовых запросов до обработки ошибок и аутентификации.
- 14 января 2025
Ошибка JavaScript «Uncaught TypeError: Cannot read property of undefined». Что делать?
Описание проблемы
Эта ошибка возникает, когда вы пытаетесь получить доступ к свойству объекта, который в данный момент имеет значение undefined
. Например:
let obj = undefined;
console.log(obj.property); // Uncaught TypeError: Cannot read property 'property' of undefined
Возможные причины
- Объект не был инициализирован. Возможно, переменная еще не была объявлена или ей не присвоено значение.
- Неправильный путь к данным. Вы пытаетесь обратиться к свойству объекта, но объект отсутствует в цепочке.
- Асинхронность. Данные могли еще не загрузиться или быть доступны в момент обращения.
- Опечатка в названии свойства. Вы могли неверно написать имя свойства объекта.
Шаги по исправлению
1. Проверка объекта перед доступом к свойствам
Убедитесь, что объект существует, прежде чем пытаться получить его свойства.
if (obj !== undefined && obj !== null) {
console.log(obj.property);
}
// Или современный способ:
console.log(obj?.property); // Вернет undefined, если obj равен null или undefined
2. Инициализация объекта перед использованием
Если переменная должна содержать объект, убедитесь, что он инициализирован.
Неверный код:
let data;
console.log(data.user.name); // Ошибка
Исправление:
let data = { user: { name: "Иван" } };
console.log(data.user.name); // "Иван"
3. Проверка API или данных с сервера
Если данные загружаются с сервера, добавьте проверку, что ответ корректен.
fetch('https://api.example.com/data')
.then(response => response.json())
.then(data => {
if (data?.user?.name) {
console.log(data.user.name);
} else {
console.error('Данные пользователя отсутствуют');
}
});
4. Использование значений по умолчанию
Для предотвращения ошибок можно задавать значения по умолчанию.
let user = undefined;
let userName = user?.name || "Гость";
console.log(userName); // "Гость"
5. Отладка с помощью console.log
Проверяйте промежуточные значения переменных в консоли браузера.
console.log(obj); // Убедитесь, что объект определен
Пример из жизни
Вы пишете код для отображения имени пользователя из объекта user
:
let user = null; // Данные еще не загружены
console.log(user.name); // Uncaught TypeError: Cannot read property 'name' of null
Исправление:
let user = null;
console.log(user?.name || "Имя пользователя не найдено"); // "Имя пользователя не найдено"
Итог
Следуя этим рекомендациям, вы сможете избежать ошибок, связанных с доступом к свойствам undefined
или null
. Если ошибка продолжает появляться, убедитесь, что данные корректно загружаются, и используйте инструменты отладки.
- 15 ноября 2024
Как исправить ошибку JavaScript «Uncaught ReferenceError: variable is not defined»
Эта ошибка возникает, когда вы пытаетесь обратиться к переменной, которая не была объявлена в текущей области видимости. Например:
console.log(myVariable); // Uncaught ReferenceError: myVariable is not defined
Возможные причины
- Вы пытаетесь обратиться к переменной до ее объявления.
- Переменная объявлена внутри функции и недоступна за ее пределами.
- Ошибка в написании имени переменной (опечатка).
Шаги по исправлению
1. Проверка объявления переменной
Убедитесь, что переменная объявлена перед ее использованием.
Неверный код:
console.log(myVariable); // Ошибка
Исправление:
let myVariable = 10;
console.log(myVariable); // 10
2. Правильное определение области видимости переменной
Если переменная объявлена внутри функции, она недоступна за ее пределами.
Неверный код:
function myFunction() {
let localVariable = "Привет";
}
console.log(localVariable); // Ошибка
Исправление:
function myFunction() {
let localVariable = "Привет";
console.log(localVariable); // "Привет"
}
myFunction();
3. Использование глобальных переменных
Если переменная должна быть доступна везде, объявляйте ее глобально (но избегайте этого, если возможно).
let globalVariable = "Глобальная переменная";
function showVariable() {
console.log(globalVariable);
}
showVariable(); // "Глобальная переменная"
4. Проверка имени переменной на ошибки
Проверьте, нет ли опечаток в имени переменной.
Неверный код:
let myVariable = "Данные";
console.log(myVarible); // Ошибка
Исправление:
let myVariable = "Данные";
console.log(myVariable); // "Данные"
5. Использование typeof
для проверки существования переменной
Вы можете использовать оператор typeof
, чтобы проверить, объявлена ли переменная.
if (typeof myVariable !== "undefined") {
console.log(myVariable);
} else {
console.log("Переменная не определена");
}
Пример из жизни
Вы пишете функцию для проверки данных пользователя:
function checkUser() {
if (userName) {
console.log(`Добро пожаловать, ${userName}!`);
}
}
checkUser(); // Ошибка: userName не определен
Исправление:
let userName = "Иван";
function checkUser() {
if (userName) {
console.log(`Добро пожаловать, ${userName}!`);
}
}
checkUser(); // "Добро пожаловать, Иван!"
Итог
Эта ошибка часто возникает из-за опечаток или неверной области видимости. Убедитесь, что переменные объявлены и доступны в нужных местах. Если необходимо, используйте typeof
для проверки их существования.
- 15 ноября 2024
Как исправить ошибку JavaScript «Uncaught TypeError: Cannot set property of undefined»
Эта ошибка возникает, когда вы пытаетесь присвоить значение свойству объекта, который не существует (имеет значение undefined
или null
). Например:
let obj;
obj.property = "value"; // Uncaught TypeError: Cannot set property 'property' of undefined
Возможные причины
- Объект не был инициализирован.
- Вы обращаетесь к объекту, который уже удален или еще не создан.
- Ошибка в цепочке данных, например, промежуточное свойство объекта равно
undefined
.
Шаги по исправлению
1. Инициализация объекта перед использованием
Убедитесь, что объект объявлен и инициализирован перед тем, как вы присваиваете его свойствам значения. Неверный код:
let obj;
obj.property = "value"; // Ошибка
Исправление:
let obj = {};
obj.property = "value"; // Работает
2. Проверка существования объекта перед доступом
Проверяйте объект на null
или undefined
, чтобы избежать ошибок. Пример:
let obj;
if (obj) {
obj.property = "value";
} else {
console.log("Объект не определен");
}
3. Использование опциональной цепочки
Если ошибка возникает в глубоко вложенных объектах, используйте опциональную цепочку. Пример:
let obj;
obj?.nestedProperty?.subProperty = "value"; // Не вызовет ошибку
4. Проверка асинхронных данных
Если объект формируется после загрузки данных, убедитесь, что данные доступны перед их использованием.
let obj;
setTimeout(() => {
obj = { property: "value" };
console.log(obj.property); // Работает
}, 1000);
// Нельзя обращаться к obj до инициализации:
console.log(obj.property); // Ошибка
Пример из жизни
Вы загружаете данные пользователя с сервера и пытаетесь установить свойство объекта:
let user;
user.name = "Иван"; // Ошибка
Исправление:
let user = {};
user.name = "Иван"; // Работает
Итог
Чтобы избежать ошибки «Cannot set property of undefined», убедитесь, что объект существует и инициализирован. Используйте проверки на null
, опциональную цепочку или инициализируйте объект перед работой с его свойствами.
- 15 ноября 2024