У меня есть стек с объектами целочисленных значений. Я хочу купить грузовик вместимостью N (N неизвестно), чтобы быть уверенным, что смогу перевезти все объекты максимум за X кругов.
Х известен. Другими словами, я должен разбить стек (порядок объектов должен поддерживаться) в максимальных X подмножествах с суммой меньше N и найти это минимальное N.
Не могли бы вы помочь мне с алгоритмом или идеей, пожалуйста? Спасибо.
Если, как вы утверждаете, «порядок объектов должен поддерживаться», то мы можем решить это с помощью бинарного поиска по N, по O(|objects| * log m), где m — общая сумма.
Бумага @hlt, на которую ссылается комментарий, о многостороннем разделении номеров, будет применяться, если порядок объектов можно изменить. В этом случае, когда порядок фиксирован, мы можем просто попробовать разные N, максимально упаковав разделы. Если выбранное нами N слишком мало, мы превзойдем X. Это делает N упорядоченным и, следовательно, доступным для поиска.
