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

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

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

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

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

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

Материалы по теме


«Доктайп» — журнал о фронтенде. Читайте, слушайте и учитесь с нами.

ТелеграмПодкастБесплатные учебники

Читать дальше

Модули Angular для организации кода и ленивой загрузки

Модули Angular для организации кода и ленивой загрузки

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

  • что такое модули в Angular;
  • зачем они нужны;
  • как их использовать для структурирования кода;
  • как реализовать «ленивую» загрузку модулей;
  • и чем отличаются Feature, Core и Shared модули.

Если вы только начинаете изучать Angular или хотите углубить свои знания, эта статья поможет вам лучше понять, как правильно организовать архитектуру Angular-приложения.

Читать дальше
JS
  • 12 мая 2025
Навигация в Angular: RouterLink, Router.navigate и Router.navigateByUrl

Навигация в Angular: RouterLink, Router.navigate и Router.navigateByUrl

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

Разберёмся, как работают RouterLink, Router.navigate и Router.navigateByUrl.

Читать дальше
JS
  • 11 мая 2025
Полное руководство по Lazy Loading в Angular

Полное руководство по Lazy Loading в Angular

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

В этом пошаговом руководстве мы разберём, как реализовать lazy loading в Angular.

Читать дальше
JS
  • 10 мая 2025
Все (ну или почти все) способы автоматически перезагрузить страницу раз в N секунд

Все (ну или почти все) способы автоматически перезагрузить страницу раз в N секунд

Иногда страницу нужно просто перезагрузить. Полностью. Не компонент, не блок, а именно целиком. Без обсуждений, без лишней логики. Например, чтобы:

  • экран с результатами обновлялся каждые 10 секунд;
  • интерфейс на стенде показывал последние данные без кнопок;
  • страницы в интранете не устаревали, пока никто не смотрит.

Это можно сделать в любой связке: HTML, JS, Python, PHP, Go, Node.js — не важно. Ну и если говорить совсем прямо, то совсем разных способов всего три, а остальное просто вариации.

Читать дальше
JS
  • 5 мая 2025
Vite 6: Новый этап в развитии фронтенд-разработки

Vite 6: Новый этап в развитии фронтенд-разработки

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

Читать дальше
JS
  • 16 января 2025
Всё, что нужно знать о работе с API в JavaScript: пошаговый разбор

Всё, что нужно знать о работе с API в JavaScript: пошаговый разбор

Работа с API — это основа веб-разработки. Если вы хотите получать данные с сервера, отправлять информацию или взаимодействовать с внешними сервисами (например, картами Google, платёжными системами или погодными сервисами), вам не обойтись без этого навыка. Разберём работу с API на практике: от базовых запросов до обработки ошибок и аутентификации.

Читать дальше
JS
  • 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. Если ошибка продолжает появляться, убедитесь, что данные корректно загружаются, и используйте инструменты отладки.

JS
  • 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 для проверки их существования.

JS
  • 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, опциональную цепочку или инициализируйте объект перед работой с его свойствами.

JS
  • 15 ноября 2024