Je werkt als zelfstandige pizzakoerier en jouw job is om pizza’s te gaan halen bij pizzeria’s en deze te gaan leveren bij klanten. Je wilt natuurlijk wel dat al dat rondrijden het ook waard is, dus je zou graag zoveel mogelijk verdienen op een dag.
De pizzeria’s hebben hun bestellingen van de dag al doorgegeven, deze krijg je allemaal samen in een grote lijst van records Order. Op de bestelling staat de locatie van de pizzeria, die van de klant, de deadline tegen wanneer deze moet geleverd worden, en hoeveel je verdient door de levering. Let op, de klanten zijn heel kieskeurig en willen hun bestelling krijgen op het exacte moment van de deadline, niet vroeger of later.
Je beschikt over een wegenplan van de stad als graaf waarbij alle locaties (pizzeria’s en klanten) toppen \((1,2,\dots,N)\) zijn en de wegen ertussen de gewogen bogen zijn. Het gewicht van een boog zegt hoe lang het duurt om deze weg af te leggen. De graaf wordt voorgesteld als een adjacentiematrix.
Gelukkig ben je een pizzakoerier die al ervaring heeft met routes zoeken, zo weet je dat het algoritme van Floyd jou kan helpen om de kortste route tussen twee locaties te vinden. Als dit is gebeurt kan je deze routes dan gebruiken om te vinden welke leveringen je moet doen om je opbrengst te maximaliseren.
Jammer genoeg is teleportatie nog niet uitgevonden en moet je altijd nog naar de pizzeria rijden voor een bestelling op te halen. let er dus op dat je ook de tijd die je nodig hebt om van de klant van de vorige bestelling naar de pizzeria van de volgende bestelling meerekent.
Implementeer de interface Courier in een klasse genaamd PizzaCourier. Hiervoor schrijf je eerst de methode public double[][] findShortestPaths(double[][] adjacency) die de lengte van de kortste route tussen elk paar toppen vindt op basis van de adjacentiematrix. Daarna moet je de methode public List<Order> maximizeProfit(double[][] paths, List<Order> orders, int home) implementeren die deze paden gebruikt, samen met een lijst bestelling om de bestellingen te vinden die je die dag gaat doen om een maximale opbrengst te hebben. Het argument home zegt je vanuit welke top je start. Voor de eerste bestelling uit te voeren moet je echter nog van thuis naar de pizzeria rijden van die bestelling.
Pas de lijst met bestellingen niet aan. Indien je dit wel doet, zullen de testen falen.
Gebruik eventueel de testklasse SimpleTest om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.