Python-сообщество

Доброго времени суток!

Прошу помощи! Есть следующая задача:
В прямоугольнике X c шириной h и высотой l требуется разместить несколько одинаковых прямоугольников Y меньшей площади с шириной a и высотой b. Необходимо реализовать алгоритм, результатом работы которого будет max кол-во Y, способное поместиться в X.

Понимаю что нужно привязываться к площади фигур и “вращать” Y в цикле, но с чего начать….. ума не приложу.
Помогите пожалуйста советом по решению.

ого. очень интересно было бы узнать как это реализовать.

PunK_HS
Доброго времени суток!

Прошу помощи! Есть следующая задача:
В прямоугольнике X c шириной h и высотой l требуется разместить несколько одинаковых прямоугольников Y меньшей площади с шириной a и высотой b. Необходимо реализовать алгоритм, результатом работы которого будет max кол-во Y, способное поместиться в X.

Понимаю что нужно привязываться к площади фигур и “вращать” Y в цикле, но с чего начать….. ума не приложу.
Помогите пожалуйста советом по решению.

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

Отредактировано doza_and (Апрель 18, 2012 22:31:35)

Я так понимаю че то типа такого?

rectangles.bmp (PS: чуть позже нормально залью)

вот быдло код:

A = 200
B = 600
# Делаем чтоб А всегда был больше B
if A < B:
    A, B = B, A
    
a = 20
b = 40
# Делаем чтоб a был всегда меньше b
if a > b:
    a, b = b, a
    
count = 0
# Рассчет количества без переворота малого прямоугольника
count = B/b + A/a
# Переворачиваем малый прямоугольник
aTURN, bTURN = b, a
# Выделяем пространство оставщееся у большого прямоугольника (т.е. сверху)
Akeep = A
Bkeep = B - B/b
count += Bkeep/bTURN + Akeep/aTURN
print u"Мне удалось разместить " + str(count) + u" прямоугольников"

Отредактировано Piton23 (Апрель 18, 2012 08:52:04)