Имеется задача по программированию:
-------------------------------------------------------------------------------
Дано (все величины - целочисленные):
- площадка X*Y
- число плиток N
- плитки прямоугольной формы.
- соотношение длин сторон плитки от a:b до b:a То есть, если a = 1 и b = 3, то возможны плитки с соотношением сторон 1:1, 1:2, 1:3, 2:1, 2:2, 2:3, 3:1, 3:2, 3:3.
- Максимальная и минимальная площади плитки - Smax и Smin. То есть, имеется ограничение плитки по размеру. Например, если Smax = 4 и Smin = 1, то возможны плитки размеров 1х1, 1х2, 1х3, 2х1, 2х2, 3х1, но не 2х3 или 4х1.
Надо замостить площадку плитками так, чтобы выполнялись следующие требования:
- все N плиток должны поместиться на площадке
- на площадке не должно остаться незакрытых мест
- размеры плиток и их расположение должны быть случайным
Желательно:
- распределение плиток должно быть равномерным
- задача должна решаться, если часть плиток (M) уже имеет заданные размеры и находится в определенных местах площадки.
В общем, должно получиться что-то такое (расцветил для наглядности):
-------------------------------------------------------------------------------
Помогите, плиз, подобрать алгоритм для решения этой задачи, ибо даже не знаю, в какую сторону копать.
Пока меня хватило только на это:
1) проверить, решаема ли задача вообще (помещаются ли N плиток на площадку): Smin * N <= X*Y