#алгоритм #любой_язык #соревнование #code_golf
Недавно закончились соревнования Яндекс.Блиц для фронтенд разработчкиов и я бы хотел
разобрать одну задачку. (Ещё раз повторюсь, что соревнования уже закончились). Как
мне показалось, задача представляет собой что-то между задачей о ранце и покрытия множества
точек отрезками. Вот её полная формулировака:
Есть девопс Петя. На работе ему нужно дежурить в определенные дни в течение последующих
100 дней. На работу Петя добирается на метро. В метро ввели билеты-абонементы, действующие
определенное количество дней со дня первой поездки по ним. Чем больше длительность
срока действия билета, тем меньше стоимость в пересчете на день. Нужно помочь Пете
сэкономить деньги и рассчитать какие билеты нужно ему купить на три месяца вперёд,
учитывая график его дежурств, таким образом, чтобы их суммарная стоимость была минимально
возможной. А еще Петя не любит носить много билетов с собой, и, если есть несколько
вариантов билетов с одинаковой минимальной стоимостью, то Пете нужен такой, в котором
меньше билетов. Если и таких вариантов окажется несколько (с одинаковой минимальной
стоимостью и количеством билетов) — то Пете подойдет любой из них.
Вам необходимо написать функцию getCheapestTickets(days, tickets), принимающую на
вход график дежурств Пети (days) и возможные варианты билетов-абонементов (tickets),
а на выходе дающую список билетов (в виде индексов из входного массива вариантов билетов),
которые нужно купить Пете.
График дежурств Пети задан в виде отсортированного массива чисел (от 1 до 100 включительно),
каждое из которых обозначает порядковый номер дня дежурства:
// Петя должен дежурить на второй, пятый, десятый и сорок пятый день относительно
текущей даты
[2, 5, 10, 45]
Каждый билет-абонемент описывается следующим интерфейсом:
interface Ticket {
// количество дней, в течение которых билет действует со дня первой поездки по
нему,
// включая этот день (от 1 до 100 включительно)
duration: number;
// стоимость билета (от 1 до 100 включительно)
cost: number;
}
Количество вариантов билетов не более 10 и гарантируется, что все билеты имеют разную
стоимость, причем, чем большее число дней действует билет, тем ниже его стоимость в
пересчёте на один день.
Формат ввода
days:
[1, 2, 4, 6, 7, 8, 9, 10, 20]
tickets:
[
{ cost: 3, duration: 1 },
{ cost: 10, duration: 7 },
{ cost: 20, duration: 30 }
]
Формат вывода
[0, 0, 1, 0]
Моя проблема заключается в том, что мои решения не проходили по времени. Сначала
я попытался решить задачу рекурсивно обходя наивно всё дерево решений (JavaScript):
const getCheapestTickets = (days, tickets) => {
// Вспомогательная функция для обхода всех вариантов билетов.
// l указывает на текущий день из массива days.
const wrapper = (l) => {
let min = null;
// Обходим все билеты.
for (let i = 0; i < tickets.length; i += 1) {
const ticket = tickets[i];
let j = l;
// Считаем количество дней, которые покрывает данный билет.
const skip = days[l] + ticket.duration;
while (skip > days[j]) {
j += 1;
}
let curr;
if (j < days.length) {
// Рекурсивно ищем решение для оставшихся дней.
curr = wrapper(j);
curr.sum += ticket.cost;
} else {
curr = { sum: ticket.cost, includes: [] };
}
const currIncludes = [i, ...curr.includes];
curr = { ...curr, includes: currIncludes };
if (min === null) {
min = curr;
} else if (
(curr.sum === min.sum && curr.includes.length < min.includes.length)
|| curr.sum < min.sum) {
min = curr;
}
}
return min;
};
return wrapper(0, 0).includes;
};
Здесь я не понимаю, как отбросить ветви решений. Не вижу пути, как её свести к классической
задаче о рюкзаке, где решение ищется через матрицу. Далее я попробовал написать то
же решение, но уже без рекурсий, так же обходя все возможные варинаты, но уже с помощью
дерева. Оно так же не проходило по времени. Помогите, пожалуйста, составить более оптимальный
алгоритм. Важно, чтобы решение было однопоточным.
Ответы
Ответ 1
Эта задача не имеет ничего общего с задачей о рюкзаке. Фундаментальное отличие в том, что в задаче о рюкзаке (или про покрытие отрезками) количество элементов ограничено, а в нашей задаче мы можем купить неограниченное количество каждого вида билета. Легко увидеть, что если в нас есть оптимальное решение для множества дней, и оптимальное покрытие, которое можно разбить на 2 части, то мы снова получим оптимальные решения для 2 подмножеств. Если они будут не оптимальными, то и наше изначальное решение не оптимальное: дни дежурства [a1, a2, ..., an, b1, b2, ..., bn] билета [.t.]....[..t..] [t]....[...t...] // оптимальное покрытие билетами отсюда следует, 2 других оптимальных покрытий: для [a1, a2, ..., an] -> [.t.] .. [..t..] для [b1, b2, ..., bn] -> [t]....[...t...] Поэтому задачу можно решать динамически используя жадную стратегию. Сложность при этом , где n - количество дней дежурства. function getCheapestTickets(days, tickets) { // функция пытается найти билет, который покроет интервал дней дежурства // начиная с days[from] заканчивая days[to] // при этом билет не должен покрывать days[from - 1] и days[to + 1] let getTicket = function (from, to) { let length = days[to] - days[from] + 1; let maxLength = 100; if (from > 0 && to < days.length - 1) maxLength = days[to + 1] - days[from - 1] + 1; for (let i = 0; i < tickets.length; i++) if (tickets[i].duration >= length && tickets[i].duration < maxLength) return i; return null; }; let solutions = {}; // каноническое решение для покрытия нуля дней solutions[-1] = { cost: 0, tickets: [] }; const maxCost = 1000000000; for (let i = 0; i < days.length; i++) { // лучшее решение для покрытия дней с days[0] до days[i] let bestDaySolution = { cost: maxCost }; // проходимся по всем лучшим решениям для меньших промежутков // и пытаемся добавить 1 билет for (let j = -1; j < i; j++) { if (solutions[j]) { let ticket = getTicket(j + 1, i); if (ticket == null) continue; let cost = solutions[j].cost + tickets[ticket].cost; let better = // если цена меньше cost < bestDaySolution.cost || // или если цена такая же, но количество билетов меньше (cost == bestDaySolution.cost && bestDaySolution.tickets.length > solutions[j].tickets.length + 1) if (better) { bestDaySolution.cost = cost; bestDaySolution.tickets = solutions[j].tickets.slice(); bestDaySolution.tickets.push(ticket); } } } if (bestDaySolution.cost != maxCost) solutions[i] = bestDaySolution; } return solutions[days.length - 1].tickets; } console.log(getCheapestTickets([1, 2, 4, 6, 7, 8, 9, 10, 20], [ { cost: 3, duration: 1 }, { cost: 10, duration: 7 }, { cost: 20, duration: 30 } ]));Ответ 2
Я расскажу про задачу, которая очень похожа на эту, но, всё-таки, отличается от неё. Возможно, это будет полезно. Факторизация числа по заданному множеству Данный репозиторий представляет собой реализацию алгоритма, позволяющий разложить число по заданному множеству чисел. Например, мы имеем набор чисел 1, 2, 2, 3, 4, 6. Сколькими способами мы можем получить число 5? Очевидно: 1, 4 1, 2, 2 2, 3 2, 3 Таким образом, мы перебрали все возможные решения. Обратите внимание, что одно из решений повторяется. Это важно учитывать и не допускать лишних повторов. Бейзлайн Давайте сопоставим набору чисел битовую маску: [0, 0, 1, 0] Тогда, чтобы получить решение, достаточно перебрать все битовые маски. Сложность такого алгоритма будет: $O(2^N)$, где $N$ - размер маски. Очевидно, что уже при 22 элементах, придётся ждать очень долго для получения всех решений. Здесь следует отметить, что любое решение может найтись довольно быстро. Но если мы хотим убедиться, что решений нет, доказать, что оно единственное или же найти все, то время выполнения алгоритма затянется. Рассмотрим прикладную задачу, которую я решал в своей практике. Задача Пусть у нас есть покупки. Мы знаем суммарную цену, т.е. общую сумму всех товаров и цену каждого товара. При этом, клиент вернул некоторые из товаров. Требуется понять, какие из товаров клиент купил. Продолжение В ряде случаев, нам хочется понимать, сколько решений есть у этой задачи? Решение Есть товары: Каждый из них сколько-то стоит: Также есть отправление и возврат: Существует решение: Включая и исключая по очереди все в решение, мы можем найти все возможные решения. Оптимизация - 1. (Задача о рюкзаке) Прочитать подробнее можно тут В данном случае, используется идея о том, что не обязательно заполнять всю матрицу, а достаточно пойти от финального решения, т.е. и рекурсивно перебрать все решения. Таким образом, мы ответим на все вопросы задачи. Проблема данного подхода в том, что мы не можем делать это итеративно, а значит нам придётся все решения хранить в памяти, а их может быть довольно много. Важно отметить, что данная задача является частным случаем задачи о рюкзаке. Задача о рюкзаке выглядит так: Есть рюкзак, у него есть вместимость, а также мы хотим в него набрать предметов максимальной стоимости так, чтобы все они поместились. При этом, у каждого предмета есть его стоимость и вес (ограничение). Потенциально ограничений в задаче может быть более одного. В нашем случае всё проще. Во-первых, вес рюкзака и ограничение в данном случае совпадают. Во-вторых, в отличие от задаче о рюкзаке, нам требуется составить из наших предметов в точности максимальный вес рюкзака. Не забываем, что вес совпадает с ограничением, либо сказать, что такого решения не существует. Оптимизация - 2 Для того, чтобы генерировать решения итеративно, предлагается отранжировать элементы. В данном случае это возможно, покуда ограничение и вес совпадают. Затем, на каждом шаге, мы будем набивать рюкзак, итерируясь от максимального элемента к минимальному и будем пересчитывать остаток. Как только остаток станет меньше 0, возвращемся к предыдущему шагу и продолжаем поиск. Если остаток равен в точности 0, то возвращаем решение, а затем, с того же места продолжаем поиск. Заметим, что данное решение работает примерно в 2 раза дольше, чем решение задачи о рюкзаке. При этом, мы можем отдавать ответы итеративно.
Комментариев нет:
Отправить комментарий