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

(0) Опять задача про рюкзак?
Получи половину веса и заполни только левую сторону. Правую заполнишь потом методом исключения документов.

иными словами, как из набора чисел максимально близко подобраться к СуммаВесов/2

самый быстрый, но не совсем оптимальный - сортируешь по убыванию. проходишься по списку и добавляешь документ туда, где в данный момент меньше. все.

где-то в интернетах должно быть порно про это...

(3) потом можно еще пару раз пройти и менять местами 2 документа с похожим весом, чтобы уменьшить разницу

а вообще прямо 100% оптимальность требуется редко когда, с практической погрешностью в 5% можно смириться (она по разному считается. когда WMS делал, сначала тоже хотел самое оптимальное размещение. но когда оно по 5-10 минут считалось, попробовал приближенный алгоритм - отрабатывал за доли секунды.)

(5) ну да, можно. но ИМХО улучшение будет не сильно большое в % соотношении

(0) все верно, но надо брать ни какой-то документ, а все по очереди, по-убыванию и положить на ту сторону, где дельта уменьшается

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

всем спасибо за ответы! может я излишне себе запарил голову, либо пятница сказывается, но, как говорится в одном из анекдотов: - "но есть нюанс!") это по сути маршрут, т.е. отрезок с точками, где каждая из точек - выгрузка документа, т.е. нужно не слепо раскидать по сторонам, но так же учесть очередность выгрузки, что бы не получилось, что одну сторону почти всю выгрузили, а другая под завязку и как итог - нехороший перекос. или это из области фантастики?) и я только насилую свой мозг за зря?)

(10) ага. а потом - порядок разгрузки со следованием по маршруту с учетом пробок...

(10) Что такое "две стороны" в контексте маршрута? Две половины машины (продольное деление)?

(12) да. левая сторона, правая сторона

(10) Это что же вы возите и на чем, если перекос так критичен?

(13) дык разгружать-то как будут? лучше от порядка разгрузки идти, а то одну сторону разгрузят - и привет

(14) еду) много еды)
(15) так о чем я и написал в (10) просто хотелось понять - это излишняя заморочка или такое может быть

(13) А разгрузка с торца, что ли?

Стеклопакеты, что ли, возите? Так там обычно с бортов разгрузка...

(16) А еда вся одинаковая или в каждом заказе индивидуальный набор? Если одинаковая, то разгружайте равномерно и проблема будет решена сама собой.

короче - сортируешь по порядку разгрузки и раскидываешь как в (3). на остальное - насрать, выигрыша не будет.

(16) А, еда! Рефрижератор, что ли, двухсекционный?

(17) там на самом деле секции на каждой стороне. то ли 3, то ли 4 с каждой стороны, но об этом речь пока не идет. холодильник на колесах)
(19) заказы могу варьироваться от пары кг до полутонны условно

(22) Тогда надо для начала поделить весь груз на две части, потом каждую часть отсортировать в порядке разгрузки. Как поделить на две части уже написали...

(23) нет, сначала порядок разгрузки. ибо может случиться так, что все разгружаем с одной стороны...

(22) Что значит, "ПОКА не идет"? Если в риале неудобно будет разгружать - то можно и не начинать.

Если два критерия учитывать, то придется определиться и с приоритетами (весовыми коэффициентами).

А ограничение по объему разве нет?
По объему всегда недобор?

(24) Тогда может так:
1. Сортируем все заказы в порядке разгрузки
2. Начинаем раскладывать - первый заказ налево, второй направо, если справа вес больше чем слева, то третий заказ налево иначе направо и т.д.

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

(28) звучит неплохо. спс. надо будет попробовать

(28) я об этом уже писал в (20)

(31) сорри - пропустил)

(28) и я в (8)

(33) так стоп) а то описание, которое было в (0) разве не тоже самое?)

(34) я его не так как бы понял, ты там брал документ не подряд по убыванию: а подбирал лучший, не?

(35) похоже на то) "есть нюанс"

(0) Это рюкзак, и к v8 алгоритм никаким боком не относится.

(33) тогда я в (3) %)

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

был ближе к центру

(40) Тогда естественно в порядке обратном разгрузке суем в тот бок, в котором меньше.

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