Нахождение максимально возможного коэффициента масштабирования для квадратов, упакованных в коробки, с учетом размеров коробки

Question

Моя проблема заключается в следующем:

У меня есть набор значений V1, V2, ... Vn У меня есть функция f(V) = g * V, где g - это коэффициент масштабирования, который отображает эти значения в другой набор значений A1, A2, ... An. Эти значения соответствуют площадям квадратов. У меня также есть переменные W (ширина) и H (высота). И, наконец, у меня есть алгоритм упаковки коробок ( Этот , если быть точным), который принимает переменные W и H и области A1 ... An и пытается найти способ упаковки области в коробке размером W x H. Если области A не слишком велики, и алгоритм упаковки блока успешно справляется с размещением областей в блоке, он возвращает позиции квадратов (координаты слева-сверху, но это не имеет значения). Если области слишком велики, ничего не вернется.

Учитывая значения V и размеры блока W и H, какое наибольшее значение g (коэффициент масштабирования в f(V)) по-прежнему подходит для блока?

Я попытался создать алгоритм, который изначально устанавливает g в (W x H) / sum(V1, V2, ... Vn). Если значения V распределены таким образом, чтобы они точно вписывались в коробку, не оставляя промежутков между ними, это немедленно дало бы мне решение. На самом деле этого никогда не происходит, но это кажется хорошей отправной точкой. С этим начальным значением g я бы вычислил значения A, которые затем подаются в алгоритм упаковки коробок. Алгоритм упаковки коробки не будет работать (ничего не вернется), после чего я уменьшу g на 0.01 (абсолютно произвольное значение, установленное методом проб и ошибок) и попробую снова. Этот цикл повторяется до тех пор, пока алгоритм упаковки коробок не будет успешным.

Хотя это решение работает, я чувствую, что должны быть более быстрые и точные способы определения g. Например, в зависимости от того, насколько велики W и H по сравнению с суммой значений V, кажется, что должен быть способ определения лучшего значения, чем 0.01, потому что, если разница очень велика алгоритм займет очень много времени, в то время как если разница будет очень мала, она будет очень быстрой, но очень грубой. Кроме того, я чувствую, что должен быть более эффективный метод, чем просто грубое принуждение. Есть идеи?

Answer 1

Вы можете использовать бинарный поиск. Если у вас есть два значения g, так что для одной (g1) упаковки существует, а для второй (g2) упаковки не существует, попробуйте значение на половине пути h = (g1 + g2) / 2. Если упаковка существует для h, вы получаете новый финал g большего размера, и вы можете сделать такую ​​же проверку с помощью h и g2. Если упаковки не существует, вы можете выполнить такую ​​же проверку со значениями g1 и h.

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

Answer 2

Я считаю, что вы на хорошем пути с вашим методом!

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

Это хорошо, потому что у тебя хорошее начальное значение. Во-первых, вы можете уменьшить g на что-то вроде 0.1 * g, проверьте, удалась ли ваша упаковка, если нет, продолжайте уменьшать с тем же шагом, в противном случае, если упаковка правильно, увеличьте g с меньшим шагом (например, step = step / 2)

В какой-то момент ваши шаги станут очень маленькими, и вы можете прекратить поиск (определение «маленький» зависит от вас)