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

Gotchas

• The seats you sell at a given price is not only limited by the amount that customers can buy, but also by the amount of seats you have left. This makes doing an iterative DP difficult, as you have to as you have to simulate selling every amount up to the maximum. This increases the calculation to weeks * seats ^2. This problem is eliminated using recursion with memoization, as we know that customers will buy all the expected tickets at a given price.

import java.util.*;
public class c {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new c().go();
	}
	int[][][] dp;
	int[]k;
	int[][]seats,prices;
	private void go() {
		int n=in.nextInt(),w=in.nextInt();
		k=new int[w+1];
		seats=new int[w+1][101];
		prices=new int[w+1][101];
		dp=new int[w+1][n+1][2];
		for(int i=w;i>=0;i--){
			k[i]=in.nextInt();
			for(int j=0;j<k[i];j++)prices[i][j]=in.nextInt();
			for(int j=0;j<k[i];j++)seats[i][j]=in.nextInt();
		}
		for(int[][] i:dp)for(int[] j:i)Arrays.fill(j, -1);
		recurse(w,n);
		System.out.println(dp[w][n][0]);
		System.out.println(prices[w][dp[w][n][1]]);
	}
	private int recurse(int w, int n) {
		if(w==-1||n==0)return 0;
		if(dp[w][n][0]!=-1)return dp[w][n][0];
		for(int i=0;i<k[w];i++){
			int s=Math.min(n, seats[w][i]);
			int v=recurse(w-1,n-s)+prices[w][i]*s;
			if(v>dp[w][n][0]){
				dp[w][n][0]=v;
				dp[w][n][1]=i;
			}
		}
		return dp[w][n][0];
	}
}