How to Determine Cheapest Commute Ticket Combinati

问题:

My local train service recently added an option for dialy commute. I am trying to determine the algorithm for finding the cheapest combination of tickets for a given set of round trips on given days.

Here is the problem in english. Given a set of days and and rides per day what combination of the following is the cheapest.

• A round trip ticket at cost w per round trip.
• A 7 day ticket at cost x for unlimited rides during 7 consecutive calendar days.
• A 30 day ticket at cost y for unlimited rides during 30 consecutive calendar days.
• A 365 day ticket at cost z for unlimited rides during 365 consecutive calendar days.

Since I am happy to restrict this to only solving for one year at a time, I think that the list of days could easily be stored in an array that looks something like this.

{0,0,1,1,1,0,0,2,1,0,0,0,4,0,1,1,...,0,1,1,5}

Where the number is equal to the number of round trips per day.

What algorithm can I use to determine the cheapest combination of tickets that covers all of the trips?

回答1:

Hints

You can do this by solving the sub-problem:

What is the cheapest combination C[k] to cover all trips from day 0 up to day k?

To compute the answer to this sub-problem you can simply consider each of the cases of buying a ticket type. By solving the problems starting at 0 and working all the way up to 365 you are allowed to use previous results when solving a sub-problem.

For example, suppose on day 100 you need to make no trips. Then the answer will be C[99] which is the cheapest way of doing the trips on the previous days.

However, suppose on day 101 you need to make 3 trips. Then the answer for C[101] will be the cheapest of:

Buy round trip tickets today: cost 3*w+C[100]
Buy a 7 day ticket 7 days ago: cost x+C[101-7]
Buy a 30 day ticket 30 days ago: cost y+C[101-30]

When you have computed C[365] you can compare this to cost z for the all year ticket.

(If during this process you ever find yourself requiring the cost C[i] for i less than 0, the value of C[i] is 0.)

回答2:

Here is my solution in python. But first, let me give some context so that the code below shall make sense.

---

Problem statement:

You want to buy public transport tickets for the upcoming month. You know the days on which you will be travelling. The month has 30 days and there are 3 types of tickets:

• 1 day ticket costs P2, valid for one day only
• 7 days ticket costs P7, valid for 7 consecutive days from day of purchase
• 30 days ticket costs P25, valid for 30 days of the month.

Example,

month_travel_days = [1,2,4,5,7,29,30]

From the example travel days, the minimum cost is P11 by buying a 7-days ticket costing P7 and then buying separately for the remaining two days of 29th and 30th costing P4.

Solve the problem of minimizing the cost of ticket purchase given any list of travel days.

---

from operator import itemgetter

#travel_dates = [1,2,4,5,7,29,30]
travel_dates = [1,3,5,8,9,10]
#travel_dates = range(30)

def normalize(data):
    L = 30
    d1 = []
    for i in xrange(L):
        d1.append(1 if (i+1) in data else 0)
    return d1

def group_func(d):
    L = len(d)
    result = []
    for i in xrange(L):
        s = sum(d[i:i+7])
        result.append((i,s))
    return result

d1 = normalize(travel_dates)
mincost = 0
while True:
    a = group_func(d1)
    a.sort(key = itemgetter(1))
    m = a[-1][1]
    if m < 4:
        break
    for q in a:
        if q[1] == m:
            w = q
            break
    d1[w[0]:w[0]+7] = [0]*7
    mincost = mincost + 7 
mincost = mincost + d1.count(1) * 2
answer = min(25,mincost)
print "minimum cost = " + str(answer)