Optimierungsproblem: Wie viele Rechtecke passen in ein größeres Rechteck?
Hallo zusammen, ich suche gerade nach einer allgemeinen Formel zur Berechnung wie viele kleine Rechtecke der Seitenlängen c und d maximal in ein größeres Rechteck der Seitenlänge a und b passen.
Bedingung ist c<=d; c<=a; c<=b und d<=a; d<=b
Die Rechtecke dürfen dabei beliebig rotiert werden.
Ich möchte das Problem so allgemein wie möglich halten, da ich einige Probleme habe, welche nochmals auf diesem Problem aufbauen und da die Anzahl an kombinierbaren kleinen Rechtecken mind. 50 und die Anzahl an kombinierbaren großen Rechtecken mind. 20 beträgt.
Anbei eine Skizze zum Problem:
Wenn mir jemand Lösungsansätze hat, auf denen ich aufbauen kann würde das schon helfen, da ich gerade auf dem Schlauch stehe.
Die kleinen Rechtecke dürfen sich nicht überlappen und dürfen nicht überstehen.
Dürfen sich die kleineren Rechtecke überlappen?
nein
a ist aber in der Skizze die längste Kante.
a>b, a>c, a>d und
b>c, b>d
sorry der Part war falsch ich bearbeite die Frage entsprechend. Richtig ist c<=d; c<=b; c>=a und d<=a; d<=b
Sind a,b,c,d aus N oder R?
Q (rationale Zahlen)
2 Antworten
Es gibt bis heute keine geschlossene Lösung für dieses Problem. Es gibt zwar Algorithmen mit der du das "Packmuster" bestimmen kannst, aber es gilt als np-Problem und wird für "große" Rechtecke in das "kleinere" hinein sollen immer schwerer zu lösen (und damit braucht der Alg. immer länger).
Wie hier schon erwähnt kannst du aber über
die abgerundete Division
Flächeninhalt Großes Rechteck / Flächeninhalt kleines Rechteck,
die maximale Anzahl bestimmen.
Nun, ein Ansatz auf den du sicher auch gekommen bist, wäre erstmal
(a*b)/(c*d) zu rechnen und das Ergebnis auf die nächstkleinere natürliche Zahl abzurunden. Damit hast du schon mal eine obere Schranke.
Dann würde ich (ich habe das noch nicht komplett durchdacht -> Sitze im Bus und die Gedanken schweifen ständig zur nächsten Klausur morgen) die seiten anschauen. Teile beispielsweise a/c. Runde auch hier das Ergebnis auf die nächstkleinere natürliche Zahl -> n und du erhältst dein Ergebnis, wie du möglichst viele Rechtecke nebeneinander legen kannst. Berechnest du dann noch simultan b/d -> m, und multiplizierst m und n hast du schon mal eine maximale Anzahl der kleinen Rechtecke, die du in das große packen kannst. Allerdings wird hier nicht die Rotation beachtet, die natürlich bei sehr kleinen, sehr dünnen Rechtecken definitiv als Lückenfüller dienen kann.
Du könntest dann noch betrachten, ob die Anzahl m*n nahe der Obergrenze liegt und abschätzen, ob du vielleicht mit irgend einer Rotation mehr rein bekommst.