Algoritmo del piano di fissaggio

Question

Ok, ho questo compito: il pavimento del bagno di John era rotto. Abbiamo una mappa di questo piano, dove "." è buon piatto, e '+' è male piastra, per esempio:

.+++ 
.+.+ 

Qui abbiamo 5 piatti rotti e 3 buoni. Ci sono due tipi di piatti, che sono venduti in negozio: piastre 1x1 e piastre 2x1. La piastra 1x1 costa A e la piastra 2x1 costa B. L'attività è: data la mappa del piano, conteggio del prezzo minimo del fissaggio al suolo.

Guardando l'esempio in alto: possiamo posizionare 2 piastre 2x1 e 1 piastra 1x1. Quindi il prezzo sarà A + 2 * B.

Ho un'idea: per ogni piastra rotta massima lunghezza delle piastre rotte collegate. Quindi il prezzo è lunghezza/2 * B + lunghezza% 2 * A.

Il problema è che davvero non so come farlo. Ho un'idea di qualche algoritmo ricorsivo, ma ci sono così tanti problemi come i cerchi:

+++ 
+.+ 
+++ 

Così ho due domande:

1. sto andando nella direzione giusta?
2. Puoi darmi qualche suggerimento sull'implementazione di questo algoritmo?

Grazie!

EDIT

C'è caso banale quando 2 * A < B, ma parliamo di non banale =)

/EDIT

Answer 1

classico problema piastrelle. È una copertura esatta ponderata, nel caso non banale (quando si usano due tessere 1x1 costa più dell'utilizzo di una piastrella 1x2), utilizzerei ZDD per risolverlo. Cerca in The Art of Computer Programming V4 1B per un esempio (domino su una scacchiera).

Sono disponibili librerie (ad esempio CUDD), quindi non è necessario implementare ZDD da zero, anche se non è troppo difficile.

Come bonus, è possibile ottenere anche altre informazioni che di solito non sono fornite da altri algoritmi, come il numero di tasselli validi senza elencarli tutti. Si generalizza facilmente anche ad altre dimensioni/forme di piastrella (3x1, 2x2, pezzo a L, ecc.).

Answer 2

Se 2 * A < = B allora questo è banale, basta coprire tutto con 1x1s.

Nel caso opposto occorre massimizzare il numero di 2x1s. Il fatto che le tessere siano esattamente 2x1 rende più facile il problema generale della piastrellatura. In particolare, ciò equivale a trovare una corrispondenza di cardinalità massima in un grafico bipartito, vedere my answer here.

Una volta trovata la configurazione massima di 2x1, devi solo coprire il resto delle tessere con 1x1s.