Fixing Floor Algorithmus

Question

Okay, ich habe diese Aufgabe: Johns Badezimmerboden war kaputt. Wir haben eine Karte dieser Etage, wo '.' gute Platte ist, und ‚+‘ ist schlecht Platte, zum Beispiel:

.+++ 
.+.+ 

Hier haben wir 5 gebrochene Platten haben, und drei gute. Es gibt zwei Arten von Platten, die im Laden verkauft werden: 1x1 Platten und 2x1 Platten. 1x1 Platte kostet A, und 2x1 Platte kostet B. Aufgabe ist: gegeben Karte des Bodens, zählen Mindestpreis der Bodenbefestigung.

Zum Beispiel oben: Wir können 2 2x1 Platten und 1 1x1 Platte platzieren. So wird der Preis A + 2 * B sein.

Ich habe eine Idee: für jede gebrochene Plattenanzahl maximale Länge der verbundenen gebrochenen Platten. Dann Preis ist Länge/2 * B + Länge% 2 * A.

Problem ist, dass ich wirklich nicht weiß, wie es geht. Ich habe eine Idee von einigen rekursiven Algorithmus, aber es gibt so viele Probleme wie Kreise:

+++ 
+.+ 
+++ 

Also ich habe zwei Fragen:

1. Bin ich in die richtige Richtung?
2. Können Sie mir Hinweise zur Implementierung dieses Algorithmus geben?

Vielen Dank!

EDIT

Es ist trivial Fall, wenn 2 * A < B, aber lassen Sie uns über nicht-trivial =)

/EDIT

Answer 1

Klassische Parkettierungsproblem sprechen. Es ist eine gewichtete exakte Deckung, im nicht-trivialen Fall (wenn zwei 1x1-Steine ​​mehr kosten als die Verwendung von 1x2-Steinen), würde ich ZDDs verwenden, um es zu lösen. Schauen Sie in The Art of Computer Programming V4 1B für ein Beispiel (Dominos auf einem Schachbrett).

Es sind Bibliotheken verfügbar (zum Beispiel CUDD), so dass Sie ZDDs nicht von Grund auf neu implementieren müssen, obwohl das auch nicht zu schwer ist.

Als Bonus können Sie auch andere Informationen erhalten, die normalerweise nicht von anderen Algorithmen geliefert werden, wie zum Beispiel die Anzahl der gültigen Tilings, ohne sie alle aufzählen zu müssen. Es verallgemeinert auch leicht zu anderen Größen/Formen der Fliese (3x1, 2x2, L-Stück, usw.).

Answer 2

Wenn 2 * A < = B dann ist das trivial, decken Sie einfach alles mit 1x1s.

Im gegenteiligen Fall müssen Sie die Anzahl der 2x1s maximieren. Die Tatsache, dass die Fliesen genau 2x1 sind, macht es einfacher als das allgemeine Fliesenproblem. Dies ist insbesondere äquivalent zum Finden einer maximalen Kardinalitätsanpassung in einem zweiteiligen Graph, siehe my answer here.

Sobald Sie die maximale Konfiguration von 2x1 gefunden haben, müssen Sie nur den Rest der Fliesen mit 1x1s abdecken.