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

Question

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

(Извините, если мой английский плох)

C # предпочтительнее.

Answer 1

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

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

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

Answer 2

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

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