Жадные алгоритмы. Задачи о размене, рюкзаке и о задачах

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

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

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

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

Задача о планировании задач

Задача: начало недели, у разработчика в бэклоге есть список задач от разных отделов, каждая из которых требует определённого времени для выполнения. Мы хотим выбрать максимальное количество задач, которые можно выполнить, учитывая ограничение по времени.

Решение: мы выбираем задачи в порядке возрастания времени выполнения и выполняем их до тех пор, пока не достигнем максимального доступного времени. Этот подход приводит к выполнению наибольшего количества задач за ограниченное время.

❗Задача не учитывает важность задач или озлобленность начальников других отделов, мы принимаем во внимание только время их выполнения. Возможно, в реальном мире весь этот код придётся переписать.

Пример кода на 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, представляющее вместимость рюкзака.

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

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

• Что такое и зачем нужны алгоритмы
• Паттерны проектирования
• Жадный алгоритм — Википедия

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