Алгоритм расчета использования дорожного покрытия

Question

Учитывая площадь определенного размера, мне нужно выяснить, сколько камней для тротуара необходимо использовать, чтобы полностью проложить область. Предположим, что у меня пустой пол из 100-метровых квадратов и камней размером 20x10 см и 30x10 см. Я должен проложить область с минимальным использованием камней обоих размеров. Кто-нибудь знает алгоритм, который вычисляет это?

(Извините, если мой английский плохо) является предпочтительным

C#.

Answer 1

Это категория проблем, известных как проблема упаковки.

Этот DevX article обеспечивает фоновые и контурные подходы без прямого решения домашней работы для вас (он также предоставляет код, но вам придется немного подумать, чтобы применить его к вашей ситуации).

Answer 2

Вы можете решить это в своей голове (при условии, что область для заполнения прямоугольная). Если вам нужно заполнить область из N квадратов, а ваши плитки - 2x1 и 3x1, вам никогда не понадобится больше двух 2x1 плиток. Это дает общее количество плиток, которые вам нужны для N/3 (округленные), за исключением случая N = 1, что невозможно.

Доказательство: Пусть ваша область А х В, а не оба A и B являются 1. Предположим, не ограничивая общности, что А = 1.

Вы можете плитка прямоугольная область А х 3 с! 3x1 плитки легко. Повторите этот шаблон, чтобы заполнить как можно больше. Если строк нет, все готово (вы пливили всю площадь с помощью плиток 3x1) Если есть одна строка слева, заполните плитки 3x1, пока у вас не останется 0, 1 или 2 пробела. 0 => вы закончили, 1 => замените последние 3x1 двумя 2x1, 2 => заполните последний квадрат 2x1. Если осталось два ряда, выполните аналогичную конструкцию. Вам останутся либо 0 столбцов (все готово), 1 столбец (заполните его 2x1), либо 2 столбца (заполните его двумя 2x1).