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

Question

проблема:

Учитывая сетку и элементы с высотой 1 и шириной 2, 3 или 4, определите, можно ли выделить новый элемент с данной шириной (w) и положением ((x1, y), (x2, y)) так, чтобы сетка имеет (и будет иметь) как можно меньше пустых ячеек между существующими и будущими элементами.

Constaints:

• Вы не можете перемещать элементы, вы можете только определить, можно ли выделить элемент с заданными положением и шириной
• Элемент с шириной j имеет k вероятности быть выделенным в будущем, ширина 2 (высокая), ширина 3 (средняя), ширина 4 (низкая)
• Вы не можете иметь более 3 элементов с одинаковым x1 или x2
• Минимизировать количество пустых ячеек между элементами вдоль оси x

Пример сетки:

Сложность в том, что я не знаю, какие элементы будут выделены, я могу только предсказать, как будет заполнена сетка, основываясь на логике вероятности, определенной выше.

Я ищу алгоритм для решения этой проблемы, любые советы приветствуются.

Большое спасибо!

Answer 1

Предположим, Grid - это 2-мерный массив, инициализированный с Empty -значениями. Решение в Python может быть:

def fitsInGrid(x1,y,w): 
  return all([Grid[x1+x,y] is Empty for x in range(w)])