Zählen der Möglichkeiten, eine Mauer mit zwei Fliesengrößen zu bauen [geschlossen]

Hier ist eine Lösung in Java, einige der Array-Längenüberprüfung usw. ist ein wenig unordentlich, aber ich bin sicher, dass Sie es ziemlich leicht verfeinern können.

In jedem Fall hoffe ich, dass dies hilft zu demonstrieren, wie der Algorithmus funktioniert: -)

Das sieht nach dem Problemtyp aus, den Sie rekursiv lösen könnten. Hier ist ein kurzer Überblick über einen Algorithmus, den Sie verwenden könnten, mit einer rekursiven Methode, die die vorherige Ebene und die Anzahl der verbleibenden Ebenen als Argumente akzeptiert:

• Beginnen Sie mit der anfänglichen Anzahl von Layern (z. B. 27x5 beginnt mit reserLayers = 5) und einer leeren vorherigen Ebene
• Testen Sie alle möglichen Layouts der aktuellen Ebene
  • Fügen Sie im nächsten verfügbaren Slot in der Ebene, die wir erstellen, ein 3x1 hinzu. Überprüfen Sie, dass (a) es nicht über die Zielbreite hinausgeht (z. B. nicht über die 27-Breite in einer 27x5) und (b) es nicht gegen die Abstandsbedingung der vorherigen Ebene
  verstößt
  • Versuchen Sie weiterhin, der aktuellen Ebene 3x1s hinzuzufügen, bis wir eine gültige Ebene erstellt haben, die genau (z. B.) 27 Einheiten breit ist
  • Wenn wir kein 3x1 im aktuellen Slot verwenden können, entfernen Sie es und ersetzen Sie es durch ein 4.5x1
  • Sobald wir eine gültige Ebene haben, dekrementieren residualLayers und geben sie zusammen mit der Ebene, die wir gerade erstellt haben, zurück in unseren rekursiven Algorithmus
• Sobald wir remainingLayers = 0 erreicht haben, haben wir ein gültiges Panel erstellt, also erhöhen Sie unseren Zähler

Die Idee ist, dass wir alle möglichen Kombinationen gültiger Layer erstellen. Sobald wir (im 27x5 Beispiel) 5 gültige Ebenen übereinander haben, haben wir ein komplettes gültiges Panel erstellt. Daher sollte der Algorithmus jedes mögliche gültige Panel genau einmal finden (und somit zählen).

Dies ist ein '2d bin packing' Problem. Jemand mit anständigen mathematischen Kenntnissen wird Ihnen helfen können oder Sie könnten ein Buch über Rechenalgorithmen ausprobieren. Es ist bekannt als "kombinatorisches NP-schweres Problem". Ich weiß nicht, was das bedeutet, aber der "harte" Teil packt meine Aufmerksamkeit:)

Ich habe mir Stahlschneidpläne angeschaut, und sie verwenden meistens eine beste Schätzung. In diesem Fall können zwar 2 x 4,5 "vertikal gestapelt 3 x 3" Zoll horizontal gestapelt aufnehmen. Sie könnten möglicherweise ohne Verschwendung davonkommen. Wird ziemlich schwierig, wenn Sie die beste Lösung - die mit minimaler Verschwendung - herausfinden müssen.

1. Finden Sie alle Möglichkeiten, um eine einzelne Zeile der angegebenen Breite zu bilden. Ich nenne das einen "Zeilentyp". Beispiel 12x3: Es gibt 4 Reihentypen der Breite 12: (3 3 3 3) , (4.5 4.5 3) , (4.5 3 4.5) , (3 4.5 4.5) . Ich würde diese als eine Liste der Lücken darstellen. Beispiel: (3 6 9) , (4.5 9) , (4.5 7.5) , (3 7.5) .

2. Suchen Sie für jeden dieser Zeilentypen, welche anderen Zeilentypen darauf passen könnten.

   Beispiel:

   a. Ein (3 6 9) passt auf (4.5 7.5) .

   b. Ein (4.5 9) passt auf (3 7.5) .

   c: Ein (4.5 7.5) passt auf (3 6 9) .

   d: Ein (3 7.5) passt auf (4.5 9) .

3. Zählen Sie aus diesen Regeln, wie Sie Stapel mit der angegebenen Höhe erstellen. Dynamische Programmierung ist dafür anwendbar, da auf jeder Ebene nur der letzte Zeilentyp und die Anzahl der Wege benötigt werden, um dorthin zu gelangen.

Edit: Ich habe das gerade in meiner Kaffeepause ausprobiert, und es funktioniert. Die Lösung für 48x10 hat übrigens 15 Dezimalstellen.

Edit: Hier sind weitere Details des dynamischen Programmteils:

Ihre Regeln aus Schritt 2 werden in ein Array möglicher Nachbarn übersetzt. Jedes Element des Arrays entspricht einem Zeilentyp und enthält die Indizes für die möglichen benachbarten Zeilentypen dieses Zeilentyps.

Im Fall von 12 × 3 hat jeder Zeilentyp nur einen einzigen möglichen benachbarten Zeilentyp, aber im Allgemeinen kann er mehr sein.

Die dynamische Programmierung beginnt mit einer einzelnen Zeile, wobei jeder Zeilentyp genau auf eine Art erscheint:

Dann wird die nächste Zeile gebildet, indem für jeden Zeilentyp die Anzahl der Möglichkeiten hinzugefügt wird, die mögliche Nachbarn in der vorherigen Zeile hätten bilden können. Bei einer Breite von 12 ist das Ergebnis wieder 1 1 1 1 . Am Ende summiere einfach die letzte Zeile.

Komplexität:

• Das Finden der Zeilentypen entspricht dem Aufzählen der Blätter eines Baumes; Es gibt ungefähr (/ width 3) Ebenen in diesem Baum, so dass dies eine Zeit von O (2 ^{w / 3} ) = O (2 ^w ) .

• Die Überprüfung, ob zwei Zeilentypen passen, dauert proportional zu ihrer Länge, O (w / 3) . Das Erstellen der Kreuztabelle ist proportional zum Quadrat der Anzahl der Zeilentypen. Dies macht Schritt 2 O (w / 3 · 2 ^{2w / 3} ) = O (2 ^w ) .

• Die dynamische Programmierung nimmt height mal die Anzahl der Zeilentypen multipliziert mit der durchschnittlichen Anzahl der Nachbarn (die logarithmisch zur Anzahl der Zeilentypen ist), O ( h · 2 ^{w / 3} · w / 3) = O (2 ^w ) .

Wie Sie sehen, wird dies alles durch die Anzahl der Zeilentypen bestimmt, die exponentiell mit der Breite wachsen. Glücklicherweise sind die konstanten Faktoren eher gering, so dass 48 × 10 in wenigen Sekunden gelöst werden kann.