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

Question

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

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

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

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

Идея моей грубой силы заключалась в том, чтобы сделать первый субарейный конец в позиции 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 (в ​​том порядке, в котором они отображаются, как я сейчас вижу эту страницу).

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

Answer 3

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

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

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

EDIT: По предложению Даниила, мы могли бы изменить размещение СТРАТЕГИИ делителя немного, чтобы поместить его, пока не дойдет до суммы элементов, как и остальных позиций слева, меньше делителей.

Answer 4

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

Начните с того, что разделители распределены равномерно (на самом деле не важно, как вы начинаете).

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

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

EDIT: см. Комментарий от @rds. Вам придется больше думать о подпрыгивающих решениях и о конечных условиях.

Answer 5

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

Оттуда

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

Answer 6

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

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