Bauklötze-Problem

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
pixewakb
User
Beiträge: 1409
Registriert: Sonntag 24. April 2011, 19:43

Ein theoretisches Problem: Sagen wir mal ich habe Bauklötze mit den Größen 6, 4 und 3 und muss daraus zwei Zahlen bilden, also z. B. einmal 13 und das andere Mal z. B. 18. Die Zahl der Bauklötze ist vorgegeben, also z. B. 2 x 6er, 4 x 4er, 1 x 3er. Jetzt soll ich prüfen, welche Kombinationsmöglichkeiten es gibt.

Gibt es für solche Aufgaben einen Algorithmus? Ist das ein Graphenproblem? Wie würdet ihr das lösen und nach welchem Wort müsste ich suchen, um einen Ansatz zu finden?

Hintergrund: Ich hatte heute ein vergleichbares Problem, das ich durch einfaches Ausprobieren (überschaubare Zahlen und Größen) bereits lösen konnte. Mich hätte hier aber mal interessiert, ob man komplexere Probleme, wo man eine Lösung nicht direkt hätte sehen können, auch mit Python lösen könnte.
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Das ist das Rucksackproblem. NP vollstaendig wenn ich mich recht erinnere.
Antworten