Plane Ticket Pricing

Introduction

This problem gives you prices to choose from (100) for each week(52), and the number of tickets that will sell at that price for that week. It asks you to compute the maximum amount of money to be made given some max of seats (300) which may be sold

Solutions

Brute force

Idea

choose all combinations of prices each week and return the max.

Gotcha

Be sure to elimnate combinations which sell too many seats!

Runtime

100^52 = 10^104

DP

Idea

Greedy is a reasonable thought, but it's clear this can't work. For instance, if we sell tickets at a high price now, and find that we can sell them for an even higher price later. Many greedy heuristics produce good solutions, but might not be optimal. When we know brute force is too slow, and greedy might cause us to make a decision which hurts us down the line, DP is the reasonable thought. So what is in our state:

DP Dimensions:

• Time, because time is almost ALWAYS a dimension
• seats left, because anytime there is some constraint that could cause an invalid solution, it's almost always a dimension

DP value:

• amount of money made, because the value is almost always the final thing we're trying to solve for

Relation:

• iterate over all possible values for that week, recurse on the next week with the right amount of fewer seats

Runtime

• 52 * 100 * 300 = 1.5 million