Как разместить прямоугольники в заданной области?

У меня есть заданная площадь (например, круг, но это может быть и треугольник). Мне нужно найти наилучшие значения Xi и Yi, чтобы эти прямоугольники покрывали как можно большую часть этой области. У меня есть заданный шаг для приращения И.

Я должен сделать это в VBA (Excel), где у меня нет такого опыта. Создание всех возможных комбинаций с помощью цикла for совершенно неэффективно и может занять несколько часов.

Мне нужен совет о том, как оптимизировать эту проблему.

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

введите здесь описание изображения


person Beni Du    schedule 04.02.2014    source источник
comment
Посмотрите на связанный вопрос с кодом Excel VBA в ответе: math.stackexchange.com/questions/606002/   -  person Axel Kemper    schedule 04.02.2014
comment
Каков ваш заданный шаг для приращения Yi?   -  person DeanBDean    schedule 04.02.2014
comment
Мой код структурирован следующим образом: от минимального_Y до максимального_Y с заданным_шагом. Сделайте Y4=минимальный_Y, Y3=Y4+данный_шаг и т. д. Здесь максимальный_Y определяется, например, радиусом. Он не может быть больше радиуса круга   -  person Beni Du    schedule 04.02.2014
comment
Как х относится к у? Пропорционально? Всегда ли есть восемь прямоугольников? Что вы подразумеваете под оптимизацией? Сократить отходы? Максимизировать у?   -  person Dick Kusleika    schedule 04.02.2014
comment
Y4=min(Y3)=Y4+step? Что ты имеешь в виду? Как может Y4=Y4+step?   -  person DeanBDean    schedule 04.02.2014
comment
Это две разностные линии Y4=minimum_Y и Y3=Y4+step   -  person Dick Kusleika    schedule 04.02.2014
comment
Всегда есть 8 прямоугольников. Оптимизация для моей задачи должна заключаться в том, чтобы максимально использовать заданную площадь круга. Кроме того, как вы можете видеть, это симметричная задача, поэтому я могу использовать только полукруг.   -  person Beni Du    schedule 05.02.2014


Ответы (1)


Наличие известного приращения для Yi означает, что, зная Y1, вы можете найти все остальные Yi, а впоследствии и все Xi (из уравнения окружности (Sum Xi)^2 + Yi^2/4 = R^2). И от них крытая площадь.

Это устанавливает связь между Y1 и целевой функцией. Сначала постройте его, чтобы увидеть, как выглядят максимумы (кусочно-гладкие, но прерывистые). Затем... вызовите команду еще раз.

Для простоты работы в Excel вы можете продолжить с фиксированным количеством прямоугольников и установить нулевое значение Xi для тех, которые выходят за пределы круга.

person Yves Daoust    schedule 04.02.2014