Жадные алгоритмы: короткий обзор
- 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
, представляющее вместимость рюкзака.
В целом, жадные алгоритмы — только один из подходов, который может пригодиться вам в работе, но далеко не единственный. Узнайте больше об этом на курсе «Алгоритмы и структуры данных» — лишним точно не будет.
Материалы по теме
«Доктайп» — журнал о фронтенде. Читайте, слушайте и учитесь с нами.
Читать дальше
Ошибка 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
Как исправить ошибку 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.
- 15 ноября 2024
300кк в наносекунду
Игра, где нужно забрать своё и продержаться ещё один день.
- 7 марта 2024
9 книг по JavaScript для начинающих в 2024
Все вокруг говорят, что книги — прошлый век. Но вовремя прочитанная хорошая книжка может здорово помочь в изучении нового языка или технологии, а то и вообще целиком объяснить какую-нибудь важную штуку. Например, какие бывают алгоритмы, или зачем нужен рефакторинг. К тому же, хоть фреймворки меняются каждый год, основы обычно долго не меняются.
Мы опросили знакомых разработчиков, узнали, что читают они сами, и предлагаем вам подборку хороших книг по JavaScript.
- 6 марта 2024
Объект 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);
- 23 января 2024
Генерация QR-кодов на JS в 4 шага. Node.js + qrcode
Давайте сделаем простой REST API на Node.js и Express, который будет генерировать QR-коды для любой ссылки. Если у вас ещё не установлены Node.js
и npm
, установите их с официального сайта.
- 22 ноября 2023
ChatGPT не справляется
Притворитесь нейросетью и решите 101 задачку по JavaScript как можно быстрее.
- 2 ноября 2023
Знакомство с JavaScript
Теперь, когда вы знаете, как создать структуру веб-страницы с помощью HTML и оформить ее стилями с помощью CSS, пришло время оживить её с помощью JavaScript (JS). JavaScript — это мощный язык программирования, который используется для создания интерактивных и динамических веб-сайтов.
Вы можете добавить JavaScript в ваш HTML-документ двумя способами:
Встроенный JavaScript: непосредственно в HTML-документ, в тегах <script>
:
<script>
alert("Привет, мир!");
</script>
Внешний JavaScript: подключение внешнего .js
файла к HTML-документу:
<script src="script.js"></script>
- 1 ноября 2023