Minimale Rechtecke, die benötigt werden, um einen gegebenen rechteckigen Bereich abzudecken
Ich habe einen rechteckigen Bereich der Dimension: n*m . Ich habe auch ein kleineres Rechteck der Dimension: x*y . Was ist die Mindestanzahl kleinerer Rechtecke, die benötigt werden, um die gesamte Fläche des größeren Rechtecks abzudecken?
Es ist nicht notwendig, die kleineren Rechte zu packen . Sie dürfen sich überlappen, überschreiten Sie bei Bedarf die Grenzen des größeren Rechtecks. Die einzige Voraussetzung ist, dass wir die geringste Anzahl von x*y Rechtecken verwenden müssen.
Eine andere Sache ist, dass wir die kleineren Rechtecke bei Bedarf drehen können (90 Grad Drehung meine ich), um die Anzahl zu minimieren.
n, m, x und y: Alle sind natürliche Zahlen. x, y müssen keine Faktoren von n, m sein.
Ich konnte es in der gegebenen Zeit nicht lösen, noch konnte ich einen Ansatz finden. Ich initiierte, indem ich verschiedene Fälle von n aufnahm, wobei m durch x, y teilbar ist.
update
Beispieltestfälle:
- n * m = 3 * 3, x * y = 2 * 2. Ergebnis sollte 4 sein
- n * m = 5 * 6, x * y = 3 * 2. Ergebnis sollte 5 sein
- n * m = 68 * 68, x * y = 9 * 8. Ergebnis sollte 65 sein
1 Antwort
(UPDATE: Siehe neuere Version unten.)
Ich denke (aber ich habe zu diesem Zeitpunkt keine Beweise), dass unregelmäßige Pflasterungen verworfen werden können, und das Finden der optimalen Lösung bedeutet, den Punkt zu finden, an dem die Richtung der Fliesen gewechselt werden muss.
Sie beginnen mit einem Grundraster wie folgt:
und die optimale Lösung wird eine dieser beiden Formen annehmen:
Für jeden dieser Punkte berechnen Sie die Anzahl der erforderlichen Kacheln für beide Optionen:
Dies ist eine sehr einfache Implementierung. Die "horizontalen" und "vertikalen" Werte in den Ergebnissen sind die Anzahl der Kacheln in der nicht gedrehten Zone (in den Bildern rosa dargestellt).
Der Algorithmus prüft wahrscheinlich einige Dinge zweimal und könnte einige Memoizations verwenden, um die Geschwindigkeit zu erhöhen.
(Tests haben gezeigt, dass Sie den Algorithmus ein zweites Mal ausführen müssen, wenn der x- und y-Parameter vertauscht ist, und dass das Überprüfen beider Lösungsarten tatsächlich notwendig ist.)
Dies ist das Gegenbeispiel, das Evgeny Kluev lieferte: (68, 68, 9, 8) welches 68 zurückgibt, während es eine Lösung mit nur 65 Rechtecken gibt, wie in diesem Bild gezeigt:
Update: Verbesserter Algorithmus
Das Gegenbeispiel zeigt den Weg für eine Verallgemeinerung des Algorithmus: Arbeiten Sie von den 4 Ecken aus, versuchen Sie alle einzigartigen Kombinationen von Orientierungen und jede Position der Grenzen a, b, c und d zwischen den Regionen; Wenn ein Rechteck in der Mitte frei gelassen wird, versuchen Sie es mit beiden Ausrichtungen:
Unten ist eine einfache, nicht optimierte Umsetzung dieser Idee; Es prüft wahrscheinlich einige Konfigurationen mehrmals, und es dauert 6,5 Sekunden für den 11 × 17/1000 × 1000 Test, aber es findet die richtige Lösung für das Gegenbeispiel und die anderen Tests von der vorherigen Version, so dass die Logik vernünftig erscheint.
Dies sind die fünf Rotationen und die Nummerierung der im Code verwendeten Regionen. Wenn das große Rechteck ein Quadrat ist, werden nur die ersten 3 Rotationen überprüft. Wenn die kleinen Rechtecke Quadrate sind, wird nur die erste Rotation überprüft. X [i] und Y [i] sind die Größe der Rechtecke in der Region i, und w [i] und h [i] sind die Breite und Höhe der Region i, ausgedrückt in der Anzahl der Rechtecke.