In deze oefening schrijven we een algoritme dat zo efficiënt mogelijk vliegtuigen toekent aan uitgaande vluchten op een vliegveld. Het vraagstuk is tweevoudig:

1. Gegeven een reeks geplande vluchten, is het mogelijk deze uit te voeren met een specifieke collectie beschikbare vliegtuigen?
2. Zo ja, wat is de optimale planning?

Men wil graag zo weinig mogelijk plaatsen leeg laten op de vliegtuigen, vooral voor langeafstandsvluchten.

Gevraagd wordt om dit vraagstuk op te lossen met een backtracking algoritme dat alle geldige oplossingen genereert en hiervan de beste teruggeeft, of aangeeft dat de beschikbare vliegtuigen niet volstaan om alle vluchten te plannen.

Een Flight¹ bestaat uit een aantal passagiers en een afstand. Een Airplane² kan een gegeven maximaal aantal passagiers (de capaciteit) vervoeren en heeft een bereik dat aangeeft hoe ver het vliegtuig kan vliegen met een volledig gevulde tank. De interface Scheduler³, die jullie implementeren in een klasse FlightScheduler legt de methode List<Airplane> schedule(List<Flight> flights, Set<Airplane> planes) op. Deze probeert een planning te maken voor de gegeven lijst van vluchten, gebruik makend van de gegeven verzameling van vliegtuigen. Is het onmogelijk om zo’n planning te maken, dan zal de methode null terug geven. Is het wel mogelijk, dan geeft ze een lijst van vliegtuigen terug die de beste planning voorstelt. Hierbij wordt het vliegtuig op plaats i in de teruggegeven lijst gebruikt voor de vlucht op plaats i in de opgegeven lijst. Als er meerdere oplossingen zijn met exact dezelfde kost, is het om het even welke hiervan je teruggeeft.

Merk op dat het niet toegestaan (en ook niet mogelijk) is om de gegeven lijst met vluchten of verzameling vliegtuigen te wijzigen! Doe je dit toch, dan zal je onvermijdelijk foutmeldingen krijgen in de tests.

De kost van een geplande vlucht is gedefinieerd als het aantal lege plaatsen vermenigvuldigd met de gevlogen afstand. We willen de som van deze kost voor alle vluchten minimaliseren, d.w.z.

\[\sum_{i = 0}^{\text{aantal vluchten}} \left( \text{capaciteit}(p_i) - \text{passagiers}(f_i) \right) \cdot \text{afstand}(f_i)\]

met \(f_i\) en \(p_i\) respectievelijk de \(i\)-de vlucht en het hiervoor gekozen vliegtuig.

Voor de duidelijkheid vermelden we hier nog enkele (voor de hand liggende) regels:

• Een vliegtuig met capaciteit \(c\) kan niet gebruikt worden voor een vlucht met meer dan \(c\) passagiers.
• Een vliegtuig met bereik \(b\) kan niet gebruikt worden voor een vlucht met afstand groter dan \(b\).
• Elk vliegtuig mag slechts eenmaal gebruikt worden, aangezien alle vluchten tegelijk gepland en vervolgens uitgevoerd worden.
• Een geldige planning geeft voor elke vlucht een vliegtuig terug, m.a.w. de teruggegeven lijst met vliegtuigen is ofwel null (geen planning mogelijk) ofwel van dezelfde lengte als de opgegeven lijst met vluchten en zal zelf nooit null-waarden bevatten, noch vliegtuigen die niet voorkomen in de gegeven verzameling.

Zoals steeds worden enkele lokale tests voorzien in SimpleTest⁴ die je eventueel zelf kan aanvullen.