Letztes Update: 17. Mai 2022
Kontext
Im Frühjahr 2021 nahm ich erfolgreich an der zweiten Runde des Bundeswettbewerbs Informatik teil. Ich durfte mir zwei der drei gestellten Aufgaben aussuchen und sie über mehrere Monate hinweg bearbeiten. Die Ergebnisse meiner bei weitem nicht perfekten Arbeit können interessierte hier einsehen und wiederverwenden.
Aufgabe 1: Flohmarkt
Hier ging es darum, Anfragen zur Miete eines Flohmarktstandplatzes so optimal auszuwählen und zu ordnen, dass die Gewinne durch Mieteinnahmen maximiert wurden.
Zur Lösung dieses modifizierten Verpackungsproblems habe ich einen gierigen Algorithmus verwendet und mehrere Heuristiken zur Verbesserung der Ergebnisse ausprobiert.
Aufgabe 2: Spießgesellen
In verdeckten Schüsseln befanden sich verschiede Obstsorten. Nun wurden verschiedene Obstspieße erstellt. Mit der Information, welche Sorten auf einem Spieß waren und welche Schüsseln benutzt wurden, um den Spieß zu bauen, sollte herausgefunden werden, welche Sorte sich in welcher Schüssel befand.
Gelöst habe ich das Problem mit einer schrittweisen, logischen Eliminierung möglicher Sorten für eine Schüssel (lieber die ausführliche Dokumentation lesen). Die Darstellung des Problems als bipartiter Graph mit anschließender Durchführung eines Matchings wäre auch ein Lösungsansatz gewesen.
.png)