Оптимальная 2d укладка в прямоугольник

[eugrita]

Рассматривается 2d-задача оптимального раскроя или мощения прямоугольниками $b , h$ прямоугольной области $B , H$ (Она же задача оптимальной (максимальной) раскладки одинаковых ящиков в 1 ряд по высоте)
Будем рассматривать не все множество укладок а только с одинаковым расположением плиток в столбцах (строках).
Частные случаи
V-укладка (прямоугольник $B , H$ мостится плитками $b , h$так что размер $ h$ вдоль $H$)
$m=[\frac{B}{b}]$ $n=[\frac{H}{h}]$ $k=m \cdot n$
H-укладка (прямоугольник $B, H$ мостится плитками $b , h$ так что размер $ b$ вдоль $H$)
$m=[\frac{B}{h}]$ $n=[\frac{H}{b}]$ $k=m \cdot n$
Общий случай
VH(i)-укладка $i$-столбцов V-укладки оставшиеся $j$ –H-укладки.
При этом $j=[\frac{B-i \cdot b}{h}]$ $k_1=i \cdot [\frac{H}{h}]$
$k_2 =j \cdot [\frac{H}{b}] $ $k=k_1+k_2 $
Далее путем расчета при разных i находится максимальное k и соответствующая пара $i,j$ задающая вид укладки. (при таких укладках неважно как чередуются V- и H-столбцы.
Примеры расчета
а) $B=30;H=40 ; b=2.6; h=3.5;$
$k = 120 , 116 , 127 , 123 , 119 , 115 , 126 , 122 , 118 , 114 , 125 , 121$
максимальное количество укладок $К=127$ получено при $i=2,j=7 $т.е при 2 рядах V-укладки и 7 рядах H-укладки
б)$B=30;H=40 ; b=2.7; h=6.1;$
$k = 56 , 62 , 68 , 60 , 66 , 58 , 64 , 56 , 62 , 54 , 60, 66$
максимальное количество укладок $К=68$ получено при $i=2,j=4 $т.е при 2 рядах V-укладки и 4 рядах H-укладки
Вопрос. Для корректности предложенного решения надо доказать или опровергнуть утверждение, что оптимальные укладки достигаются именно на множестве VH(i)-укладок а не на каких-то иных

[Dmitriy40]

eugrita в сообщении #1237564 писал(а):

Для корректности предложенного решения надо доказать или опровергнуть утверждение, что оптимальные укладки достигаются именно на множестве VH(i)-укладок а не на каких-то иных

По моему данное утверждение опровергается примером: 4 прямоугольника 2х3 в квадрат 5х5, укладка по или против часовой стрелки с шагом 90°, не является VH (какова вообще нереализуема).
С другой стороны, полно конфигураций когда именно VH укладка будет оптимальной.
Т.е. истинность утверждения зависит от (соотношения) параметров задачи.
PS. Если бы эта задача решалась настолько просто (VH укладкой), она не была бы NP-полной.

[Someone]

Я не очень понял, что означает

eugrita в сообщении #1237564 писал(а):

$m=[\frac{B}{b}]$ $n=[\frac{H}{h}]$ $k=m \cdot n$

Вы не догадались применить какие-нибудь знаки препинания?

eugrita в сообщении #1237564 писал(а):

Для корректности предложенного решения надо доказать или опровергнуть утверждение, что оптимальные укладки достигаются именно на множестве VH(i)-укладок а не на каких-то иных

Как насчёт укладки плиток $2\times 3$ в прямоугольник $5\times 5$?

P.S. Пока писал, тот же контрпример предложил Dmitriy40.
P.P.S. Знак умножения в виде косого креста кодируется "\times".

[Dmitriy40]

Someone в сообщении #1237571 писал(а):

Я не очень понял, что означает

Имхо это попытка получить количество вмещающихся элементов, только квадратные скобки должны означать округление вниз до целого и по идее, eugrita, изображаться другими скобочками: $m=\left\lfloor \frac{B}{b} \right\rfloor$.

[eugrita]

$m=[\frac{B}{b}]$ [] - обозначают целую часть , $m$ мах возможное количество рядов
$n=[\frac{H}{h}]$ -мах возможное количество плиток в одном ряду

Да я понимаю задача сложная и оптимальное решение при отдельных соотношениях размеров не
на VH(i) укладках. Но все таки хочется выделить максимально общие утверждения когда можно все таки ограничиться VH(i) укладками

[Someone]

Dmitriy40 в сообщении #1237573 писал(а):

изображаться другими скобочками

Проблема не в скобочках (у математиков квадратные скобки вокруг числа как раз и означают функцию "целая часть", то есть, "округление вниз"). Я же прямо написал, что проблема в знаках препинания.

(Оффтоп)

P.S. И вы оба нарушаете правила записи формул.

[eugrita]

---

-- Чт авг 03, 2017 09:52:15 --

1)обнаружил что даже в этой постановке задача недоделана
(рассматривались одинаковые укладки $b,h$ и $h,b$ только по столбцам.
Но можно и нужно сравнивать с одинаковыми укладками по строкам.
Поэтому немного меняю терминологию принятую сначала
Vh-укладка (прямоугольник BxH мостится плитками bxh так что размер h вдоль H)
Vb-укладка (прямоугольник BxH мостится плитками bxh так что размер b вдоль H)
(здесь однотипные укладки, поэтому не важно как мостится - по строкам или по столбцам)
Комбинированная укладка по столбцам
Vhb(i)-укладка по столбцам. i-столбцов Vh-укладки оставшиеся j – Vb -укладки.
Комбинированная укладка по строкам
Hhb(i)-укладка по строкам. i-строк размером h вдоль B, оставшиеся j размером b вдоль B
2) ниже приведены расчеты по скорректированной программе частично с рис-пояснениями

и более крупных укладок