Ermitteln der optimalen Kachelungsstrategie mit Quadraten unterschiedlicher Größe

Dies erfordert eine dynamische Programmierlösung. Ich nehme an, wir haben ein square[r][c] Array von booleschen Werten, was wahr ist, wenn (r, c) ein 1x1 Quadrat hat (Ich habe die Lösung vereinfacht, um mit 1x1, 2x2, 4x4 und 8x8 Quadraten zu arbeiten, um es einfacher zu machen, aber es ist leicht anzupassen). Pad es mit einer Wand von false Sentinel-Werte in der oberen Zeile und linke Spalte.

Definieren Sie ein zweidimensionales count -Array, wobei count[r][c] sich auf die Anzahl der 1x1-Quadrate in der Region oberhalb und links von (r, c) bezieht. Wir können sie mit einem dp-Algorithmus addieren:

Das obige funktioniert, indem wir zwei Regionen addieren, von denen wir bereits die Summe kennen, die doppelt gezählte Fläche subtrahieren und die neue Zelle hinzufügen. Mit dem count -Array können wir testen, ob eine quadratische Region vollständig in 1x1-Quadrate in konstanter Zeit mit einer ähnlichen Methode abgedeckt ist:

Wir erstellen dann ein zweites 2d min_squares -Array, wobei min_squares[r][c] sich auf die minimale Anzahl von Quadraten bezieht, die benötigt werden, um die ursprünglichen 1x1-Quadrate abzudecken. Diese Werte können mit einem anderen dp berechnet werden:

Um das Kacheln zu rekonstruieren, das benötigt wird, um das berechnete Minimum zu erhalten, verwenden wir ein Hilfsfeld size_used[r][c] , mit dem wir die Größe des auf (r, c) platzierten Quadrats verfolgen können. Daraus können wir das Tiling rekursiv rekonstruieren:

Sehen Sie sich vielleicht Optimaler Weg, um eine zellbasierte Form in eine minimale Anzahl von Rechtecken zu partitionieren - wenn ich das richtig verstanden habe, ist das das gleiche Problem, aber für Rechtecke anstelle von Quadraten.