Фиксирующий алгоритм пола

Question

Хорошо, у меня есть эта задача: пол ванной комнаты у Джона был сломан. У нас есть карта этого этажа, где «.» хорошая пластинка, и «+» плохая пластина, например:

.+++ 
.+.+ 

Здесь мы имеем 5 разбитых тарелок и 3 хорошие. Есть два вида тарелок, которые продаются в магазине: пластины 1x1 и 2x1 пластины. Плата 1x1 стоит A, а плата 2x1 стоит B. Задача: приведенная карта пола, минимальная цена крепления пола.

Посмотрите на пример сверху: мы можем разместить 2 пластины 2x1 и 1 пластину 1x1. Таким образом, цена будет A + 2 * B.

У меня есть идея: для каждой разбитой пластины подсчитывается максимальная длина подключенных сломанных пластин. Тогда цена длина/2 * B + длина% 2 * A.

Проблема в том, что я действительно не знаю, как это сделать. У меня есть идея некоторых рекурсивного алгоритма, но есть так много проблем, как круги:

+++ 
+.+ 
+++ 

Поэтому у меня есть два вопроса:

1. я иду в правильном направлении?
2. Можете ли вы дать мне какие-либо намеки на реализацию этого алгоритма?

Спасибо!

EDIT

Существует тривиальный случай, когда 2 * A < B, но давайте говорить о нетривиальной =)

/EDIT

Answer 1

Классическая проблема плиточные. Это взвешенная точная обложка, в нетривиальном случае (при использовании двух 1x1 плиток стоит больше, чем с использованием одной плитки 1x2), я бы использовал ZDD для ее решения. Смотрите на примере The Art of Computer Programming V4 1B (домино на шахматной доске).

Доступны библиотеки (например, CUDD), поэтому вам не нужно реализовывать ZDD с нуля, хотя это тоже не слишком сложно.

В качестве бонуса вы также можете получить другую информацию, которая обычно не предоставляется другими алгоритмами, такими как количество допустимых тилингов без их перечисления. Он также легко обобщается на другие размеры/формы плитки (3x1, 2x2, L-образный и т. Д.).

Answer 2

Если 2 * A < = B, тогда это тривиально, просто накройте все 1x1s.

В противном случае вам необходимо увеличить число 2x1. Тот факт, что плитки в точности равны 2x1, делает ее проще, чем общая проблема с черепицей. В частности, это эквивалентно нахождению согласования максимальной мощности в двудольном графе, см. my answer here.

Как только вы найдете максимальную конфигурацию 2x1, вам просто нужно покрыть остальную часть плитки 1x1.