Jetzt wo ich deine Lösung so sehe: Vermutlich könnte man auch was mit
dynamische Programmierung erreichen.
Gerade, wenn die Sollwerte klein und die Anzahl der möglichen Kombinationen groß ist, sollte das etwas bringen.
Das könnte so aussehen: Für jeden Aufbettungswert kleiner des Soll-Werts wird nur die beste Zusammenstellung aus den Listen gespeichert. In jeder Iteration wird ein Element aus den Restlisten genommen und mit allen möglichen/sinnvollen Faktoren auf die aktuelle Zusammenstellung addiert. Ungültige Zwischenergebnisse werden weggeschmissen und alle optimalen Zwischenergebnisse für die nächste Iteration aufgehoben.
Das Interessante an dieser Lösung: Du braucht nur Anzahl der Listen viele Iterationen und die Liste der optimalen Zwischenergebnisse wird für ein Soll-Wert von [n, m, k] höchstens (n+1)*(m+1)*(k+1) groß
Und gesucht ist die billigste Kombination aus Aufbettungsoptionen, die genau die notwendige Bettenzahl abdeckt.
Das finde ich eine etwas merkwürdige Einschränkung. Mehr Betten sollten doch auch OK sein
Aber ist vermutlich nicht von dir beeinflussbar
EDIT/
OT:
Da werde ich wohl einfach noch ein paar Semester warten, dann kommt das bestimmt auch im Studium.
So als Tipp, wenn du die Wahl hast: Theoretische Informatik und (algorithmische) Graphentheorie sind
imho ziemlich interessant für Informatiker, die sich für Algorithmen interessieren, die über das Sortieren von Listen hinaus gehen
Wenn du mal in der DP herum guckst, findest du unter den schwierigeren Themen jede Menge Optimierungsprobleme und Sachen, die sich durch Graphen modellieren lassen. Abgesehen von den typischen kombinatorischen Problemen, die auch von der theoretischen Informatik behandelt werden.