Алгоритм поиска минимального числа N для разбиения значений стека на подмножества X с суммой ниже, чем N

Question

У меня есть стек с целочисленными значениями объектов. Я хочу купить грузовик грузоподъемностью N (N неизвестен), чтобы быть уверенным, что смогу перевозить все объекты на максимальных X кругах.

Х известен. Другими словами, я должен разделить стек (порядок объектов должен быть сохранен). В максимальных подмножествах X с суммой, меньшей N, и найти этот минимум N.

Можете ли вы помочь мне с алгоритмом или идеей, пожалуйста? Спасибо.

Answer 1

Если, как вы утверждаете, «порядок объектов должен поддерживаться», тогда мы можем решить это с помощью двоичного поиска по N, в O(|objects| * log m), где m - общая сумма.

Статья @hlt, на которую ссылается комментарий, касающаяся многоканального разбиения номеров, будет применяться, если порядок объектов можно изменить. В этом случае, когда порядок фиксирован, мы можем просто попробовать разные N s, упаковывая разделы как можно больше. Если N, который мы выберем, слишком мал, мы в итоге превзойдем X. Это делает N упорядоченным и, следовательно, доступным для поиска.