Okay, ich habe diese Aufgabe: Johns Badezimmerboden war kaputt. Wir haben eine Karte dieser Etage, wo '.' ist eine gute Platte, und "+" ist eine schlechte Platte, zum Beispiel:
%Vor%Hier haben wir 5 zerbrochene Teller und 3 gute Teller. 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: gegebene Karte des Bodens, zählen Mindestpreis der Bodenbefestigung.
Zum Beispiel oben: Wir können 2 2x1 Platten und 1 1x1 Platte platzieren. Also wird der Preis A + 2 * B sein.
Ich habe eine Idee: für jede gebrochene Plattenanzahl maximale Länge der verbundenen gebrochenen Platten. Dann ist der Preis Länge / 2 * B + Länge% 2 * A .
Problem ist, dass ich wirklich nicht weiß, wie es geht. Ich habe eine Idee von einem rekursiven Algorithmus, aber es gibt so viele Probleme wie Kreise:
%Vor%Ich habe also zwei Fragen:
Danke!
BEARBEITEN
Es gibt einen trivialen Fall, wenn 2 * A & lt; B, aber lass uns über nicht-triviale =)
sprechen/ BEARBEITEN
Klassisches Tiling-Problem. Es ist eine gewichtete exakte Deckung, im nicht-trivialen Fall (wenn zwei 1x1-Steine mehr kosten als die Verwendung einer 1x2-Kachel), würde ich ZDDs verwenden, um sie zu lösen. In Die Kunst der Computerprogrammierung V4 1B nach einem Beispiel (Dominosteine 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 bekommen, die normalerweise nicht von anderen Algorithmen geliefert werden, wie die Anzahl der gültigen Tilings, ohne sie alle aufzuzählen. Es verallgemeinert auch leicht zu anderen Größen / Formen der Fliese (3x1, 2x2, L-Stück, usw.).
Wenn 2 * A & lt; = B, dann ist das trivial, decken Sie einfach alles mit 1x1s ab.
Im umgekehrten 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 zur Suche nach einer maximalen Kardinalitätsanpassung in einem zweiteiligen Graphen, siehe meine Antwort hier .
Sobald Sie die maximale Konfiguration von 2x1 gefunden haben, müssen Sie nur den Rest der Kacheln mit 1x1s abdecken.
Tags und Links algorithm