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

Question

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

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

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

Answer 1

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

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