前端开发者的Yandex.Blitz竞赛最近结束了，我想分析一个问题。（我再次重申，比赛已经结束）。在我看来，这个问题介于背包问题和用线段覆盖一组点之间。这是它的完整措辞：
有一个 devops Petya。在工作中，他需要在接下来的 100 天内在某些日子值班。彼佳乘地铁上班。订阅票被引入地铁，从第一次乘坐之日起的一定天数内有效。门票的持续时间越长，每天的费用就越低。我们需要帮助 Petya 省钱，并在考虑到他的值班时间的情况下，提前三个月计算出他需要购买哪些票，以使他们的总成本尽可能低。彼佳也不喜欢随身携带很多票，如果有几种最低成本相同的票，那么彼佳需要一张票少的。如果有多个这样的选项（最低成本和门票数量相同），那么其中任何一个都适合 Petya。getCheapestTickets(days, tickets)，它将 Petya 的值班表 ( days) 和可能的订阅票选项 ( tickets) 作为输入，并作为输出给出 Petya 需要购买的票列表（以票选项输入数组中的索引的形式）。Petya 的值班时间表以排序后的数字数组形式给出（从 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;
};
在这里，我不明白如何丢弃决策分支。我看不出如何将其简化为经典的背包问题，通过矩阵寻求解决方案。接下来，我尝试编写相同的解决方案，但没有递归，也绕过所有可能的变化，但在树的帮助下。也没有及时过去。请帮助制定更优化的算法。解决方案是单线程的，这一点很重要。
