Нужна идея для решения этого алгоритма головоломки

Question

В прошлом я сталкивался с подобными проблемами, и до сих пор не знаю, как решить эту проблему. Проблема выглядит так:

Вам дан массив натуральных чисел с размером n <= 1000 и k <= n, который представляет собой количество смежных подмассивов, на которые вам придется разбить ваш массив. Вы должны вывести минимум m, где m = max {s [1], ..., s [k]}, а s [i] - сумма i-го подмассива. Все целые числа в массиве находятся в диапазоне от 1 до 100. Пример: </p>

Input:                           Output:
5  3  >> n = 5 k = 3             3
2 1 1 2 3

Разбиение массива на 2 + 1 | 1 + 2 | 3 минимизирует м.

Моя идея грубой силы состояла в том, чтобы сначала завершить первый подмассив в позиции i (для всех возможных i), а затем попытаться разбить остальную часть массива на k-1 подмассивов наилучшим возможным способом. Тем не менее, это экспоненциальное решение и никогда не будет работать.

Так что я ищу хорошие идеи для ее решения. Если у вас есть, пожалуйста, скажите мне.

Спасибо за вашу помощь.

Answer 1

Вы можете использовать динамическое программирование для решения этой проблемы, но на самом деле вы можете решить с помощью жадного и двоичного поиска по ответу.Сложность этого алгоритма O(n log d), где d - выходной ответ.(Верхняя граница будет суммой всех элементов в массиве.) (Или O( n d ) в размере выходных битов)

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

Какой-то псевдокод:

// binary search
binary_search ( array, N, k ) {
    lower = max( array ), upper = sum( array )

    while lower < upper {
        mid = ( lower + upper ) / 2

        // if the greedy is good
        if partitions( array, mid ) <= k
           upper = mid
        else
           lower = mid
    }
 }

 partitions( array, m ) {
    count = 0
    running_sum = 0

    for x in array {
       if running_sum + x > m
          running_sum = 0
          count++
       running_sum += x
    }
    if running_sum > 0
       count++
    return count
 }

Это должно быть проще, если придумать концептуально.Также обратите внимание, что из-за монотонной природы функции разделов вы можете фактически пропустить бинарный поиск и выполнить линейный поиск, если уверены, что вывод d не слишком велик:

 for i = 0 to infinity
    if partitions( array, i ) <= k
       return i

Answer 2

Динамическое программирование.Создайте массив

int best[k+1][n+1];

, где best[i][j] - лучшее, что вы можете получить, разбив первые j элементы массива int i подмассивы.best[1][j] - это просто сумма первых j элементов массива.Имея строку i, вы вычисляете строку i+1 следующим образом:

for(j = i+1; j <= n; ++j){
    temp = min(best[i][i], arraysum[i+1 .. j]);
    for(h = i+1; h < j; ++h){
        if (min(best[i][h], arraysum[h+1 .. j]) < temp){
            temp = min(best[i][h], arraysum[h+1 .. j]);
        }
    }
    best[i+1][j] = temp;
}

best[m][n] будет содержать решение.Алгоритм O (n ^ 2 * k), возможно, возможно что-то лучшее.

Редактировать: комбинация идей ChingPing, toto2, Coffee on Mars и rds (в ​​том порядке, в котором они отображаются, как я сейчассм. эту страницу).

Set A = ceiling(sum/k).Это нижняя граница для минимума.Чтобы найти хорошую верхнюю границу для минимума, создайте хороший раздел любым из упомянутых методов, перемещая границы до тех пор, пока не найдете простое движение, которое все еще уменьшает максимальную сумму.Это дает вам верхнюю границу B, не намного большую, чем нижняя граница (если бы она была намного больше, я думаю, вы бы легко достигли улучшения, переместив границу).Теперь перейдем к алгоритму ChingPing, с известной верхней границей, уменьшающей количество возможных ветвей.Эта последняя фаза O ((BA) * n), находка B неизвестна, но я думаю, что лучше, чем O (n ^ 2).

Answer 3

У меня есть отстойный алгоритм ветвей и границ (пожалуйста, не понижайте меня)

Сначала возьмите сумму массива и dvide на k, что даст вам наилучшую оценку для вашего ответа, то есть среднее значение A. ТакжеМы сохраним лучшее решение, которое мы видели до сих пор для любой ветви GO (глобальный оптимальный). Давайте рассмотрим, что мы ставим делитель (логический) как единицу разбиения после некоторого элемента массива, и мы должны поставить k-1 разбиений.Теперь мы будем жадно расставлять разбиения следующим образом:

Пройдите по элементам массива, суммируя их, пока не увидите, что в следующей позиции мы превысим A, теперь сделаем две ветви одну, в которой вы поместите делитель в эту позицию ив другом месте, где вы ставите на следующую позицию, сделайте это рекурсивно и установите GO = min (GO, ответьте за ветку).Если в любой точке какой-либо ветви у нас есть раздел, больший, чем GO, или no of position меньше, чем оставленные для размещения разделы, которые мы связываем.В конце у вас должно быть GO, когда вы отвечаете.

РЕДАКТИРОВАТЬ: Как предложено Дэниелом, мы могли бы немного изменить стратегию размещения разделителей, чтобы разместить ее, пока вы не достигнете суммы элементов как Aили оставшиеся оставшиеся позиции меньше делителей.

Answer 4

Это просто набросок идеи ... Я не уверен, что она работает, но она очень проста (и, вероятно, слишком быстра).

Вы начинаете говорить, расставляя разделения равномерно (на самом деле не имеет значения, с чего начать).

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

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

РЕДАКТИРОВАТЬ : см.комментарий @rds.Вам придется больше думать о прыгающих решениях и конечном состоянии.

Answer 5

Моя идея, которая, к сожалению, не работает:

1. Разделить массив на N подмассивов
2. Найти два смежных подмассива, сумма которых наименьшая
3. СлияниеПодмассивы, найденные на шаге 2, образуют новый непрерывный подмассив
4. Если общее количество подмассивов больше k, повторите итерацию с шага 2, иначе завершите.

Answer 6

Если в вашем массиве есть случайные числа, вы можете надеяться, что раздел, в котором каждый подмассив имеет n / k, является хорошей отправной точкой.

Оттуда

1. Оцените этот вариант решения, вычисляя суммы
2. Сохраните это решение.Например, с:
   • массивом индексов каждого подмассива
   • соответствующего максимума суммы по подмассивам
3. Уменьшить размериз максимального подмассива: создайте два новых кандидата: один с подмассивом, начинающимся с индекса + 1;один с подмассивом, заканчивающимся на index-1
4. Оцените новых кандидатов.
   • Если их максимум выше, отбросить
   • Если их максимум ниже, выполнить итерацию на 2, за исключением случаев, когда этот кандидат уже был оценен, и в этом случае это решение.