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

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

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

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

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

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

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


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

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

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

9 книг по JavaScript для начинающих в 2024

9 книг по JavaScript для начинающих в 2024

Все вокруг говорят, что книги — прошлый век. Но вовремя прочитанная хорошая книжка может здорово помочь в изучении нового языка или технологии, а то и вообще целиком объяснить какую-нибудь важную штуку. Например, какие бывают алгоритмы, или зачем нужен рефакторинг. К тому же, хоть фреймворки меняются каждый год, основы обычно долго не меняются.

Мы опросили знакомых разработчиков, узнали, что читают они сами, и предлагаем вам подборку хороших книг по JavaScript.

Читать дальше
JS
  • 6 марта 2024
Объект URL в JavaScript: полный разбор

Объект URL в JavaScript: полный разбор

Объект URL в JavaScript представляет URL-адрес и предоставляет удобные методы для работы с ним. Он позволяет анализировать, конструировать и декодировать URL-адреса.

Создать объект URL можно двумя способами:

Конструктор URL() — самый распространённый способ, в котором вы передаёте любой URL в виде строки в качестве аргумента.

const url = new URL("https://www.example.com/path?query=123#hash");

Использование window.location — это глобальный объект в браузерах, который содержит информацию о текущем URL.

const currentUrl = new URL(window.location.href);
Читать дальше
JS
  • 23 января 2024
Знакомство с JavaScript

Знакомство с JavaScript

Теперь, когда вы знаете, как создать структуру веб-страницы с помощью HTML и оформить ее стилями с помощью CSS, пришло время оживить её с помощью JavaScript (JS). JavaScript — это мощный язык программирования, который используется для создания интерактивных и динамических веб-сайтов.

Вы можете добавить JavaScript в ваш HTML-документ двумя способами:

Встроенный JavaScript: непосредственно в HTML-документ, в тегах <script>:

<script>
  alert("Привет, мир!");
</script>

Внешний JavaScript: подключение внешнего .js файла к HTML-документу:

<script src="script.js"></script>
Читать дальше
JS
  • 1 ноября 2023
Событие onclick в JS на примерах

Событие onclick в JS на примерах

Интерактивность — ключевой компонент любого современного сайта. И одним из наиболее часто используемых событий для создания интерактивности является событие onclick. В этой статье мы подробно разберёмся, что такое событие onclick, как его использовать и приведем примеры применения.

Событие onclick — это событие JavaScript, которое активируется, когда пользователь кликает на определенный элемент страницы. Это может быть кнопка, ссылка, изображение или любой другой элемент, на который можно нажать.

Читать дальше
JS
  • 30 октября 2023
Как перевернуть сайт. Самая короткая инструкция

Как перевернуть сайт. Самая короткая инструкция

Не представляем, зачем это может понадобиться, но не могли пройти мимо.

Никакой магии. Мы вызываем JavaScript-функцию rotateBody(), которая применяет свойство transform с значением rotate(180deg) к элементу <body>. Когда вы нажмете на кнопку «Перевернуть», всё, что находится внутри <body> будет повернуто на 180 градусов (то есть, встанет вниз головой)

function rotateBody() {
  document.body.style.transform = 'rotate(180deg)';
}

<button onclick="rotateBody()">Перевернуть</button>

Но такой код повернёт страницу только один раз. Если нужно, чтобы она возвращалась обратно при втором клике, усложним код:

let isRotated = false;

function rotateBody() {
  if (isRotated) {
    document.body.style.transform = 'rotate(0deg)';
    document.body.style.direction = "ltr";
  } else {
    document.body.style.transform = 'rotate(180deg)';
    document.body.style.direction = "rtl";
  }
  isRotated = !isRotated;
}

Надеемся, вы прочитали это описание до того, как нажать на кнопку.

JS
  • 25 октября 2023
Как узнать геолокацию: Geolocation API

Как узнать геолокацию: Geolocation API

Geolocation API позволяет сайтам запрашивать, а пользователям предоставлять свое местоположение веб-приложениям. Геолокация может использоваться для выбора города в интернет-магазине, отображения пользователя на карте или навигации в ближайший гипермаркет.

Основной метод Geolocation API — getCurrentPosition(), но есть и другие методы и свойства, которые могут пригодиться.

Читать дальше
JS
  • 16 октября 2023
Что такое localStorage и как им пользоваться

Что такое localStorage и как им пользоваться

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

До localStorage разработчики часто использовали cookies, но они были не очень удобны: мало места и постоянная передача данных туда-сюда. LocalStorage появился, чтобы сделать процесс более простым и эффективным.

Читать дальше
JS
  • 12 октября 2023