The problem of covering a set of points with segments (or the knapsack problem)
Recently, the Yandex.Blitz competition for frontend developers ended, and I would like to analyze one problem. (Once again, the competition is over). It seemed to me that the problem is something between the knapsack problem and covering a set of points with segments. Here is its full wording:
There is a devops Petya. At work, he needs to be on duty on certain days for the next 100 days. Petya takes the metro to work. The metro introduced tickets-season tickets that are valid for a certain number of days from the day of the first trip on them. The longer the ticket validity period, the lower the cost per day. We need to help Petya save money and calculate what tickets he needs to buy for three months in advance, taking into account the schedule of his duties, so that their total cost is the lowest possible. And Petya does not like to carry a lot of tickets with him, and if there are several options for tickets with the same minimum price If the cost is low, then Petya needs one that has fewer tickets. If there are several such options (with the same minimum cost and number of tickets), then any of them will suit Petya.
You need to write a function getCheapestTickets(days, tickets) that accepts as input the duty schedule of Petya (days) and possible options for season tickets (tickets), and at the output gives a list of tickets (in the form of indexes from the input array of ticket options) that Petya needs to buy.
Petya's duty schedule is set as a sorted array of numbers (from 1 to 100 inclusive), each of which indicates the ordinal number of the day of duty:
// Петя должен дежурить на второй, пятый, десятый и сорок пятый день относительно текущей даты
[2, 5, 10, 45]
Each subscription ticket is described by the following interface:
interface Ticket {
// количество дней, в течение которых билет действует со дня первой поездки по нему,
// включая этот день (от 1 до 100 включительно)
duration: number;
// стоимость билета (от 1 до 100 включительно)
cost: number;
}
The number of ticket options is no more than 10 and it is guaranteed that all tickets have different prices, and the more days a ticket is valid, the lower its cost in terms of one day.
Input format
days:
[1, 2, 4, 6, 7, 8, 9, 10, 20]
tickets:
[
{ cost: 3, duration: 1 },
{ cost: 10, duration: 7 },
{ cost: 20, duration: 30 }
]
Output format
[0, 0, 1, 0]
My problem the problem is that my decisions did not pass in time. First, I tried to solve the problem recursively by naively traversing the entire decision tree (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;
};
Here I don't understand how to drop the decision branches. I don't see a way to reduce it to the classical knapsack problem, where the solution is sought through a matrix. Next, I tried to write the same solution, but without recursions, also bypassing all possible variations, but with the help of a tree. It also did not pass in time. Please help me, create a more optimal algorithm. It is important that the solution is single-threaded.
2 answers
This task has nothing to do with the backpack task. The fundamental difference is that in the backpack problem (or about covering segments), the number of elements is limited, and in our problem, we can buy an unlimited number of each type of ticket.
It is easy to see that if we have an optimal solution for a set of days, and an optimal coverage that can be divided into 2 parts, then we will again get optimal solutions for 2 subsets. If they are not optimal, then our initial solution is not optimal:
дни дежурства [a1, a2, ..., an, b1, b2, ..., bn]
билета [.t.]....[..t..] [t]....[...t...] // оптимальное покрытие билетами
отсюда следует, 2 других оптимальных покрытий:
для [a1, a2, ..., an] -> [.t.] .. [..t..]
для [b1, b2, ..., bn] -> [t]....[...t...]
Therefore, the problem can be solved dynamically using a greedy strategy. The complexity is 
n is the number of days of duty.
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 }
]));I will tell you about a task that is very similar to this one, but still different from it. Perhaps this will be useful.
Factorization of a number over a given set
This repository is an implementation of an algorithm that allows you to decompose a number into a given set of numbers. For example, we
have a set of numbers 1, 2, 2, 3, 4, 6. How many ways can we get the number 5? Obviously:
1, 4
1, 2, 2
2, 3
2, 3
So we went through all the possible solutions. Please note note that one of the solutions is repeated. This is important to take into account and avoid unnecessary repetitions.
Baseline
Let's match a set of numbers with a bit mask:
[0, 0, 1, 0]
Then, to get a solution, it is enough to iterate through all the bitmasks. The complexity of such an algorithm will be: $O (2^N)$, where $N$ - the size of the mask. Obviously, even with 22 elements, you will have to wait a very long time to get all the solutions.
It should be noted here that any solution can find it pretty quickly. But if we want to make sure that there are no solutions, to prove that it is the only one, or to find all of them, the execution time of the algorithm will be delayed.
Let's consider an applied problem that I solved in my practice.
Task
Let us have purchases. We know the total price, i.e. the total sum of all the goods and the price of each product. At the same time, the customer returned some of the goods. You need to understand which of the products the customer is using bought.
Continued
In some cases, we want to understand how many solutions there are to this problem?
Solution
There are products:
Each of them is worth something:
There are also departures and refunds available:
There is a solution:
By including and excluding one by one everything in the solution, we can find all possible solutions. decisions.
Optimization - 1. (The backpack problem)
Read more here In this case, the idea is used that it is not necessary to fill in the entire matrix, but rather to go from the final solution, i.e., and recursively iterate through all the solutions. This way, we will answer all the questions of the task. The problem with this approach is that we can't do it iteratively, which means that we will have to store all the solutions in memory, and there can be quite a lot of them.
Important note that this problem is a special case of the backpack problem. The backpack problem looks like this:
There is a backpack, it has a capacity, and we also want to collect items of the maximum value in it so that they all fit. At the same time, each item has its cost and weight (limit). Potentially, the constraints in the task can be be more than one.
In our case, everything is simpler. First, the weight of the backpack and the restriction in this case they match.
Secondly, unlike the backpack problem, we need to make up exactly the maximum weight of the backpack from our items. Do not forget that the weight coincides with the constraint, or say that there is no such solution.
Optimization - 2
In order to generate solutions iteratively, it is proposed to rank the elements. In this case, this is possible as long as the limit and the weight are the same. Then, at each step, we will fill the backpack, iterating from the maximum element to the minimum and we will recalculate the remainder. As soon as the remainder is less than 0, go back to the previous step and continue the search. If the remainder is exactly 0, then we return the solution, and then, from the same place, we continue the search.
Note that this solution works about 2 times longer than the solution of the backpack problem. At the same time, we can give the answers iteratively.