A small ferry has seats places. Tickets cost fare and are not refunded, so the ferry company is paid for every ticket it sells, whether or not the passenger turns up. Each ticket holder turns up with probability show, independently of the others. If more passengers turn up than there are seats, every passenger who cannot board is paid compensation of penalty.
Selling a few more tickets than seats earns more fares but risks compensation. Write best_tickets(seats, show, fare, penalty, max_tickets) that tries every number of tickets s from seats to max_tickets and returns a tuple (s, profit, risk) for the s with the largest expected profit:
profitis the expected profitfare · s - penalty · E[number of passengers left behind],riskis the probability that at least one passenger is left behind.
If several values of s give the same expected profit (within 1e-9), return the smallest of them.
Examples
Input: seats = 10, show = 0.8, fare = 100, penalty = 300, max_tickets = 20
Output: (12, 1096.920784896, 0.274877906944)
Explanation: with 11 tickets someone is left behind only if all 11 turn up (0.8^11 = 0.0859),
so the expected profit is 1100 - 300 · 0.0859 = 1074.23. With 12 tickets, one passenger is
left behind with probability 0.2062 and two with probability 0.1374: the expected number
is 0.3436 and the profit 1200 - 103.08 = 1096.92. Selling 13 or more earns less.
Input: seats = 5, show = 1.0, fare = 50, penalty = 50, max_tickets = 9
Output: (5, 250.0, 0.0)
Explanation: everybody turns up, so each extra ticket earns 50 and costs 50: every s ties,
and the smallest is chosen.
Constraints
1 <= seats <= max_tickets <= 4000 <= show <= 1,0 <= fare, penalty <= 10**4- floats are compared with a tolerance of
1e-6
Goals
- Compute the expected value of a function of a binomial count, not just of the count
- Weigh a sure gain against an expected cost
- Search over a decision to maximise an expected value