Algorithm to find the most valuable combination?

Question

I'm working on a small project where I need help in finding the best and cheapest tickets based on some input from the user:

• Between what periods (start & end date)?
• Within that period, are you skipping 1 or several dates?
• How many times do you need to use the ticket each day?

There are x number of tickets. A ticket can cover:

1. Single ticket, to be used only once, price $5.
2. Period ticket (unlimited rides each day), to be used as much as you want from 1 day/$10, 3 days/$30, 7 days/$45..

I guess I'm looking for some kind of algorithm to determine the best combination of tickets based on periods (including or excluding skipping dates), and also their price.

Also, I guess there needs to be considered the case where it will be a better and cheaper outcome for me to buy a period ticket that covers more days than I actually need, but is cheaper based on how many rides I'm going for each day...

UPDATE (based on Petr suggestion..)

<?php


$tickets = array(
    array("price"=>5, "label"=>"single", "period"=>null),
    array("price"=>10, "label"=>"1 day", "period"=>1),
    array("price"=>30, "label"=>"3 days", "period"=>3),
    array("price"=>45, "label"=>"7 days", "period"=>7)
);

$trips = 2;
$startDate = new DateTime("2015-06-23");
$endDate = new DateTime("2015-06-30");
$endDate->modify("+1 day");

$interval = DateInterval::createFromDateString('1 day');
$period = new DatePeriod($startDate, $interval, $endDate);

$cost = array();
$day = 1;

foreach( $period as $date ){
    $span = $startDate->diff($date);
    $days = ( $span->format('%a') + 1 );

    $ticket = getCheapestTicket( $days );
    $cost[ $day ] = $ticket;

    $day++;
}


function getCheapestTicket( $days ){
    global $tickets, $trips;

    $lowestSum = null;
    $cheapestTicket = null;

    echo "-- getCheapestTicket --" . PHP_EOL;
    echo "DAYS TO COVER: " . $days . " / TRIPS: " . $trips . PHP_EOL;

    foreach( $tickets as $ticket ){
        $price = $ticket['price'];
        $period = $ticket['period'] ? $ticket['period'] : -1;

        if( $ticket['period'] ){
            $units = ceil( $days / $period );
            $sum = round( $units * $price );
        }else{
            $units = ceil( $days * $trips );
            $sum = round( ( $days * $price ) * $trips );
        }

        if( $sum <= $lowestSum || !$lowestSum ){

            if( $ticket['period'] > $cheapestTicket['period'] ){
                $cheapestTicket = $ticket;
                $lowestSum = $sum;
            }else{
                $lowestSum = $sum;
                $cheapestTicket = $ticket;
            }

        }

        echo "TICKET: " . $ticket['label'] . " / Units to cover days: " . $units . " / Sum: " . $sum . " / Period: " . $period . PHP_EOL;
    }

    echo "CHEAPEST TICKET: " . $cheapestTicket['label'] .
    " / PRICE PER UNIT: " . $cheapestTicket['price'] . " / SUM: " . $lowestSum . PHP_EOL. PHP_EOL;

    return $cheapestTicket;

}

I'm not sure if this is on the way yet :)

Answer 1

You can solve this problem using a dynamic programming approach.

Firstly, for simplicity of the algorithm, let's for each l calculate the cheapest single ticket that can be used to cover l consecutive days. For your example this will be: 1 day $10, 2 days $30 (buy a 3-day ticket and use it only for 2 days), 3 days $30, 4-7 days $45, etc. (There will obviously be some maximal value of l beyond which there will be no such ticket.) Denote these results as cost[l].

Now the main dynamic programming solution. For each date i in your [begin, end] range, calculate ans[i] = the minimal cost to buy tickets to cover at least interval from begin to i.

Assuming that you have already calculated all the values before date i, calculation for date i is simple. You will need some ticket that ends on day i. Let's say it covers length of l days, then the price for this last ticket will be cost[l], and you will also have to cover the days from begin to i-l, which will cost ans[i-l] (or zero if i-l is before begin). So for a given i iterate over all possible ls and find the one that minimizes the solution.

This gives you the O(NL) solution, where N is the number of days and L is the maximal span of a single ticket.

This all assumes that each ticked covers several full consecutive days. If it covers, say, 24 full hours (from the hour of buying to the same hour next day), then just calculate answers for each hour.

Answer 2

Lets assume you have all the data stored in some array of days and each day has the number of rides for that day written down.

Side note: I am going to relax the conditions of a ticket lasting 24 hours and just assume each periodical ticket is good for that date (i.e, not starting at 15:00 and lasting until 14:59 the next day). This could be fixed by looking at it as hourly time units instead of days.

Sub optimal solution:
Now lets assign to all the days the cost of buying one ride tickets for that day and then start iterating over the array and checking whether or not you could substitute some of them with a cheaper ticket. You finish when no changes are done. The problem here is you might miss the optimal solution. You might assign two 3-day tickets (days 1-3 and 7-9) where a 7-day ticket (2-8) and two 1-day tickets would be better.

Tree solution: (data in leafs)
The tree option would be to arrange it in a tree with each sub tree holding the best solution for that sub tree. Then, each subtree root could check if using a ticket "covering" only part of the subtree could be useful, when taking into account the values of the roots of the parts left out.
Maybe a rank tree would come in handy here.

Answer 3

As from my example, based on what @Petr said, I don't really know how it can solve the situation where for example the period covers 8 days (2 trips each day) and you end up with a result like this:

-- getCheapestTicket --
DAYS TO COVER: 8 / TRIPS: 2
TICKET: single / Units to cover days: 16 / Sum: 80 / Period: -1
TICKET: 1 day / Units to cover days: 8 / Sum: 80 / Period: 1
TICKET: 3 days / Units to cover days: 3 / Sum: 90 / Period: 3
TICKET: 7 days / Units to cover days: 2 / Sum: 90 / Period: 7
CHEAPEST TICKET: 1 day / PRICE PER UNIT: 10 / SUM: 80

Where it should give me a result of this combination:

7 days, $45
1 day, $10

Or is this what you mean when you said "(There will obviously be some maximal value of l beyond which there will be no such ticket.)"?

Would be really sweet to get another round of explanation on your thoughts!