Сколько билетов каждого типа должен купить пассажир, чтобы общее количество поездок было не меньше n и суммарная

Данная задача связана с оптимальным выбором количества билетов каждого типа для минимизации стоимости и обеспечения требуемого количества поездок. Для ее решения будет использован метод динамического программирования.

Мы можем представить задачу в виде двумерной таблицы, где на горизонтальной оси будут числа от 0 до n, а на вертикальной оси - количество билетов каждого вида. Значения таблицы будут обозначать минимальную суммарную стоимость билетов при заданных значениях.

Пусть у нас есть пять видов билетов, их стоимости обозначим как a, b, c, d и e.

Для заполнения таблицы, начнем с нулевых значений. Для 0 поездок и 0 билетов каждого вида, стоимость будет равна 0.

Затем будем проходить по каждому возможному количеству поездок и для каждого количества поездок посчитаем минимальную стоимость билетов.

Для этого будем последовательно увеличивать количество билетов каждого вида и обновлять значения в таблице. Мы будем использовать следующее правило: для каждого значения n и каждого вида билетов будем искать минимум из двух вариантов - либо использовать билет этого вида, либо не использовать его.

Таким образом, значения в ячейках таблицы будут обновляться следующим образом:
\[
\text{{table}}[n][\text{{type}}] = \min\left(\text{{table}}[n][\text{{type}}-1] + \text{{cost}}[\text{{type}}], \text{{table}}[n-\text{{trips}}[\text{{type}}]][\text{{type}}] + \text{{cost}}[\text{{type}}]\right),
\]
где
\begin{align*}
\text{{trips}}[\text{{type}}] &\text{{ - количество поездок, которое покрывает один билет типа }} \text{{type}}, \\
\text{{cost}}[\text{{type}}] &\text{{ - стоимость одного билета типа }} \text{{type}}.
\end{align*}

После заполнения всей таблицы, ответом на задачу будет являться последний элемент таблицы, т.е. \(\text{{table}}[n][5]\). Также мы можем восстановить путь к ответу, просматривая ячейки таблицы в обратном порядке.

Приведем реализацию данного решения на языке программирования Python:

python

def find_min_tickets(n):

    trips = [0, 1, 2, 3, 4]  # количество поездок, которое покрывают билеты каждого типа

    cost = [0, a, b, c, d, e]  # стоимость билетов каждого типа



    table = [[0] * 6 for _ in range(n + 1)]

    

    for i in range(1, n + 1):

        table[i][0] = float("inf")



    for i in range(1, n + 1):

        for j in range(1, 6):

            if i >= trips[j]:

                table[i][j] = min(table[i][j-1] + cost[j], table[i - trips[j]][j] + cost[j])

            else:

                table[i][j] = table[i][j-1]

    

    tickets = [0] * 5

    total_trips = n

    

    while total_trips > 0:

        if total_trips >= trips[5] and table[total_trips][5] == table[total_trips - trips[5]][5] + cost[5]:

            tickets[4] += 1

            total_trips -= trips[5]

        elif total_trips >= trips[4] and table[total_trips][5] == table[total_trips - trips[4]][5] + cost[4]:

            tickets[3] += 1

            total_trips -= trips[4]

        elif total_trips >= trips[3] and table[total_trips][5] == table[total_trips - trips[3]][5] + cost[3]:

            tickets[2] += 1

            total_trips -= trips[3]

        elif total_trips >= trips[2] and table[total_trips][5] == table[total_trips - trips[2]][5] + cost[2]:

            tickets[1] += 1

            total_trips -= trips[2]   

        elif total_trips >= trips[1] and table[total_trips][5] == table[total_trips - trips[1]][5] + cost[1]:

            tickets[0] += 1

            total_trips -= trips[1]

    

    return tickets

Чтобы использовать эту функцию, нужно вызвать `find_min_tickets(n)`, где `n` - количество поездок.

Пример:
\(\text{{find\_min\_tickets(10)}}\) вернет \([0, 1, 0, 0, 2]\), что означает, что пассажир должен купить 1 билет второго типа и 2 билета пятого типа для обеспечения не меньшего, чем 10 поездок и минимальной стоимости.