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

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

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

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

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

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

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


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

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

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

Ошибка 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

Как исправить ошибку JavaScript «Uncaught SyntaxError: Unexpected token»

Эта ошибка возникает, когда интерпретатор JavaScript сталкивается с неожиданным токеном (символом) в коде, который нарушает синтаксические правила. Например:

let obj = { key: "value", }; // Uncaught SyntaxError: Unexpected token }

Возможные причины

  • Лишние или пропущенные символы, такие как запятые, точки с запятой, кавычки или скобки.
  • Неправильное использование синтаксиса, например, забытые конструкции или операторы.
  • Смешение разных типов кавычек (например, двойных и одинарных) без соблюдения правил их вложенности.

Шаги по исправлению

1. Проверка корректности синтаксиса

Убедитесь, что все запятые, точки с запятой и кавычки находятся на своих местах. Неверный код:

let obj = { key: "value", }; // Лишняя запятая

Исправление:

let obj = { key: "value" }; // Правильный синтаксис

2. Проверка закрытия скобок

Проверьте, закрыты ли все фигурные, круглые и квадратные скобки. Неверный код:

if (true {
    console.log("Ошибка!");
}

Исправление:

if (true) {
    console.log("Исправлено!");
}

3. Проверка типов кавычек

Не смешивайте одинарные и двойные кавычки. Неверный код:

let str = "Привет'; // Ошибка

Исправление:

let str = "Привет"; // Или let str = 'Привет';

4. Использование отладчика

Откройте консоль браузера или отладчик в вашей IDE, чтобы найти строку с ошибкой. Она будет указана в сообщении об ошибке.

// В консоли может быть указано:
Uncaught SyntaxError: Unexpected token } at script.js:10

Исправьте строку, где произошла ошибка.

5. Проверка работы кода в строгом режиме

Добавьте "use strict"; в начало вашего файла или функции, чтобы браузер проверял ваш код на соответствие строгому синтаксису.

"use strict";
let obj = { key: "value" };
console.log(obj);

Пример из жизни
Вы пытаетесь использовать стрелочную функцию, но забыли закрыть скобки:

const add = (a, b => {
    return a + b;
};

Исправление:

const add = (a, b) => {
    return a + b;
};

Итог
Чтобы избежать ошибок «Unexpected token», всегда проверяйте синтаксис вашего кода на наличие лишних или пропущенных символов, используйте инструменты отладки и следите за правильным использованием конструкций JavaScript.

JS
  • 15 ноября 2024
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