Алгоритм упаковки бина — практическая вариация

Я пытаюсь решить странную проблему с упаковкой мусорного ведра. Ссылка на оригинальную проблему Вот
(извините за длинный вопрос, спасибо за ваше терпение)

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

У меня есть N ячеек (2D прямоугольники) (N <= 40) Для каждой ячейки существует минимальная высота (minHeight [i]) и минимальная ширина (minWidth [i]). Сама панель также имеет ограничение MAXIMUM_HEIGHT.

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

Кроме того, ширина каждого столбца определяется максимальным значением minWidths каждого блока в этом столбце.

Кроме того, высота каждого столбца должна быть одинаковой. Это решает высоту панели

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

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

MAXIMUM_HEIGHT панели = 2100 мм, диапазон минимальной ширины (от 350 до 800 мм), диапазон минимальной высоты (от 225 до 2100 мм)

Согласно выбранному ответу, я сформулировал целочисленную линейную программу. Однако, учитывая комбинаторный характер проблемы, решатель, кажется, «зависает» при N> 20.

Я сейчас пытаюсь реализовать решение для обхода.

Ячейки отсортированы в порядке убывания minWidths. Если minWidths равны, то они сортируются в порядке убывания их minHeights.
Затем я решаю это с помощью First Fit убывающая эвристика. Это дает мне верхнюю границу общей ширины панели и список текущей ширины столбца.

Теперь я пытаюсь уменьшить ширину панели и разместить свои фидеры на панели меньшего размера. (Я могу проверить, правильно ли вписываются питатели в заданный список ширины столбцов)

Ширина панели может быть уменьшена следующими способами:
1. Возьмите любой столбец, замените его столбцом следующего нижнего устройства подачи minWidth. Если столбец уже имеет минимальную minWidth, попробуйте удалить его и проверить.
2. Возьмите любой столбец, замените его на столбец с более высокой подачей minWidth и удалите другой столбец.
3. Любым другим способом, я не знаю, буду рад, если кто-нибудь может указать.

Я правильно реализовал 1-й способ. Ниже приведен код. Однако я не могу правильно указать другой путь в коде.

for ( int i = 0; i < columnVector.size(); i++ ) {

QVector< Notepad::MyColumns > newVec( columnVector );
if ( newVec[i].quantity > 0
&& ( i > 0 || newVec[i].quantity > 1 ) ) {

newVec[i].quantity--;

if ( i < columnVector.size() - 1 )
newVec[i+1].quantity++;

float fitResult = tryToFit( newVec, feederVector );
myPanelWidth = fitResult ? fitResult : myPanelWidth;

if ( fitResult ) { // if feeders fit, then start the iteration again.

columnVector = newVec;
i = -1;
}
}
}

Любая помощь будет принята с благодарностью.

Спасибо

1

Решение

попробуй это https://stackoverflow.com/a/21282418/2521214

  • и поменяйте местами оси x, y
  • потому что это решение минимизирует высоту страницы (фиксированная ширина страницы)
  • если вы не хотите границы, установите ее на ноль

это в основном то, что вы кодируете сейчас

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]