Find list of tickets with best price sum I have an optimization problem, where i need to find set of tickets for certain period, such that sum of prices for these tickets is minimal.
Algo should accepts list of trips and list of tickets as input. And output list of tickets with min possible sum price with conditions that this list of tickets covers all trips.
Trip has following fields:
OriginZone
DestinationZone
EndOfTripTimestamp

Ticket object consists of these fields:
OriginZone
DestinationZone
MaxNumberOfTransfers  // 0 if limited by duration
MaxDuration           // 0 if limited by transfers
Price

It's considered that ticket covers trip if Ticket.OriginZone =&lt; Trip.OriginZone and Ticket.DestinationZone &gt;= Trip.DestinationZone. Example:
Ticket {OriginZone: 1, DestinationZone: 4, MaxNumberOfTransfers: 1, MaxDuration: 0} covers trip {OriginZone: 2, DestinationZone: 3}
MaxNumberOfTransfers specifies how much times this ticket can be used. If value it's value is 2, this ticket can cover 2 trips that happen between OriginZone and DestinationZone. MaxDuration specifies period in seconds, in which this ticket can be used from time of purchase(for example if ticket is valid for 24 hours, this field will be set to 24 * 3600). It should be considered that ticket was bought right before first trip that it's used for.
This fields are exclusive. So if MaxDuration field is set, than MaxNumberOfTransfers is not used.
Here is example, of how this algo should work:
&gt; trips = [
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T15:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-16T16:00:00},
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T17:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-17T18:00:00}
]
&gt; tickets = [
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
]
&gt; algo(trips, tickets)
OUTPUT:
  {OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
  {OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},

To clarify this example, here you see 4 trips that happened in period of 2 days. In first day there's 3 trips overall, 2 from zone 1 to 2, and one from zone 3 to 4. And on second day there's one trip from zone 3 to 4. So algorithm picks 2 tickets to cover these trips -- 24 hour ticket for zones 1 to 2 and ticket with 2 transfers for zones 3 to 4.
Overall this looks like combinatorial optimization problem, but i wasn't able to find any non trivial algorithm for solving it. So, currently i'm using brute force algo that looks like:
recursive_function(trips, tickets):
    trip = trips[0]
    find best price iterating over tickets:
        price, tickets_list = recursive_function(trips[1:], tickets)

   return tickets_list with best price sum

So, my question is, is there any common problem that's similar to my and have non-trivial solution? Or maybe someone can recommend me some topics to look closely into.
If you wanted to solve it in practice, I would recommend that you try using an ILP solver.  You can express this as an instance of integer linear programming, then use an off-the-shelf ILP solver.
Introduce zero-or-one variables $x_i$ (indicates whether the $i$th ticket is bought or not) and $y_{ij}$ (indicates whether the $i$th ticket is used to cover the $j$th trip).  Then you can write linear inequalities to express the requirements; e.g., $\sum_j y_{ij} \le d_i x_i$ where $d_i$ is the max duration of ticket $i$, and so on.  The total price is a linear function of the variables, so you can minimize that objective function, subject to these inequalities.
I don't know whether there is a more efficient algorithm.