Ответ 1
Состав
Дано:
- для каждой ячейки
i = 1, ..., M, (min) widthW_iи (min) heightH_i - максимально допустимая высота любого стека,
T
Мы можем сформулировать смешанную целочисленную программу следующим образом:
minimize sum { CW_k | k = 1, ..., N }
with respect to
C_i in { 1, ..., N }, i = 1, ..., M
CW_k >= 0, k = 1, ..., N
and subject to
[1] sum { H_i | C_i = k } <= T, k = 1, ..., N
[2] CW_k = max { W_i | C_i = k }, k = 1, ..., N
(or 0 when set is empty)
Вы можете выбрать N как любое достаточно большое целое число (например, N = M).
Алгоритм
Подключите эту смешанную целочисленную программу к существующему программному решателю смешанных целых чисел, чтобы определить сопоставление между ячейками, заданное с помощью оптимальных значений C_i, i = 1, ..., M.
Это та часть, которую вы не хотите изобретать самостоятельно. Используйте существующий решатель!
Примечание
В зависимости от выразительной мощности вашего пакета решений для смешанных целочисленных программ вы можете или не сможете напрямую применять формулировку, описанную выше. Если ограничения [1] и [2] не могут быть указаны из-за их "основанного на наборе" характера или max, вы можете вручную преобразовать формулировку в эквивалентный менее декларативный, но более -канонический, который не нуждается в этой выразительной силе:
minimize sum { CW_k | k = 1, ..., N }
with respect to
C_i_k in { 0, 1 }, i = 1, ..., M; k = 1, ..., N
CW_k >= 0, k = 1, ..., N
and subject to
[1] sum { H_i * C_i_k | i = 1, ..., M } <= T, k = 1, ..., N
[2] CW_k >= W_i * C_i_k, i = 1, ..., M; k = 1, ..., N
[3] sum { C_i_k | k = 1, ..., N } = 1, i = 1, ..., M
Здесь переменные C_i from before (принимающие значения в { 1, ..., N }) заменены на переменные C_i_k (принимая значения в { 0, 1 }) в соответствии с соотношением C_i = sum { C_i_k | k = 1, ..., N }.
Окончательное сопоставление между ячейками описывается C_i_k: cell i принадлежит в столбце k тогда и только тогда, когда C_i_k = 1.