Разделить массив по порядку

Ответ 1

Возможное решение DP:

Пусть dp[i, j] = minimum number possible if we put the first i numbers into j containers.

dp[i, j] = min{dp[p, j - 1] + numRed[p+1, i]*numBlues[p+1, i]}, p = 1 to i - 1

Ответ будет в dp[n, k].

int blue = 0, red = 0;
for (int i = 1; i <= n; ++i)
{
    if (buttons[i] == 1)
        ++red;
    else
        ++blue;

    dp[i][1] = red * blue;
}

for (int i = 2; i <= n; ++i)
    for (int j = 2; j <= k; ++j)
    {
        dp[i][j] = inf;

        for (int p = 1; p <= i; ++p)
            dp[i][j] = min(dp[p][j - 1] + getProd(p + 1, i), dp[i][j]);
    }

return dp[n][k];

Сложность будет O(n^3*k), но можно уменьшить до O(n^2*k), выполнив getProd запустите в O(1) с помощью определенных предварительных вычислений ( hint: use dp[i][1]), Я отправлю его завтра, если никто не выяснит, что на самом деле это было неправильно до тех пор.

Также возможно уменьшить до O(n*k), но для этого, вероятно, потребуется другой подход...

Ответ 2

Если я правильно понял вопрос, если у каждого контейнера есть хотя бы одна кнопка, вы можете выбрать любой контейнер, чтобы положить оставшиеся кнопки. Учитывая это, поместите одну кнопку в каждый контейнер, убедившись, что есть по крайней мере, один контейнер с красной кнопкой и по крайней мере один с голубой кнопкой. Затем с помощью остальных кнопок поместите все красные кнопки в контейнер с красной кнопкой и поместите все синие кнопки в контейнер с синими кнопками. Это сделает так, чтобы каждый контейнер имел по крайней мере одну кнопку, и каждый контейнер имеет только один цвет кнопок. Тогда каждая оценка контейнера равна 0. Таким образом, сумма равна 0, и вы минимизировали комбинированный балл.

Ответ 3

Предупреждение: считается неоптимальным

Как насчет жадного алгоритма, чтобы заставить людей говорить? Я не стану пытаться доказать это оптимальным на данный момент, но это способ приблизиться к проблеме.

В этом решении мы используем G для обозначения числа смежных областей одного цвета в последовательности кнопок. Скажем, у нас было (я использую x для красного и o для синего, так как R и B выглядят слишком похожими):

x x x o x o o o x x o

Это даст G = 6. Позвольте разбить это на группы (красный/синий), где для начала каждая группа получает целую область согласованного цвета:

3/0  0/1  1/0  0/3  2/0  0/1  //total value: 0

Когда G <= k, у вас есть минимум нуля, так как каждая группа может перейти в свой собственный контейнер. Предположим теперь, что G > k. Наш жадный алгоритм будет, в то время как есть больше групп, чем контейнеров, сверните две группы рядом в одну, что приведет к наименьшему значению контейнера delta (valueOf(merged(a, b)) - valueOf(a) - valueOf(b)). Скажем k = 5 с нашим примером выше. Наш выбор:

Collapse 1,2: delta = (3 - 0 - 0) = 3
         2,3: delta = 1
         3,4: delta = 3
         4,5: delta = 6
         5,6: delta = 2

Итак, мы разрушаем 2 и 3:

3/0  1/1  0/3  2/0  0/1  //total value: 1

И k = 4:

Collapse 1,2: delta = (4 - 0 - 1) = 3
         2,3: delta = (4 - 1 - 0) = 3
         3,4: delta = (6 - 0 - 0) = 6
         4,5: delta = 2

3/0  1/1  0/3  2/1   //total value: 3

k = 3

4/1  0/3  2/1  //total value: 6

k = 2

4/1  2/4  //total value: 12

k = 1

6/5  //total value: 30

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

Контрпример: Благодаря Jules Olléon для предоставления контр-примера, который мне было слишком ленив, чтобы думать:

o o o x x o x o o x x x

Если k = 2, оптимальное отображение

2/4  4/2  //total value: 16

Посмотрим, как к нему подходит жадный алгоритм:

0/3  2/0  0/1  1/0  0/2  3/0  //total value: 0

0/3  2/0  1/1  0/2  3/0  //total value: 1

0/3  3/1  0/2  3/0  //total value: 3

0/3  3/1  3/2  //total value: 9

3/4  3/2  //total value: 18

Я оставлю этот ответ, поскольку он достиг своей единственной цели - заставить людей говорить о решении. Интересно, может ли жадная эвристика использоваться в известном алгоритме поиска, таком как A *, чтобы улучшить время выполнения исчерпывающего поиска, но это не обеспечило бы полиномиальное время выполнения.

Ответ 4

Я всегда прошу разъяснить постановку проблемы в интервью. Представьте, что вы никогда не ставили голубые красные кнопки вместе. Тогда сумма равна 0, как и n == k. Итак, для всех случаев, когда k > 1, минимум равен 0.

Ответ 5

Вот что я понимаю до сих пор: алгоритм состоит в обработке последовательности значений {R, B}. Он может выбрать значение в текущем контейнере или следующем, если есть следующий.

Сначала я задал пару вопросов, чтобы прояснить то, что еще не знаю:

• Известно ли k и n алгоритму заранее? Я так полагаю.

• Знаем ли мы полную последовательность кнопок заранее?

• Если мы не знаем последовательность заранее, следует ли минимизировать среднее значение? Или максимум (наихудший случай)?

Идея для доказательства алгортима Марк Петерсом

Изменить: Идея для доказательства (извините, не могла поместиться в комментарии)

Пусть L (i) - длина i-й группы. Пусть d (i) - это diff, который вы получаете, свертывая контейнер я и я + 1 = > d (i) = L (i) * L (i + 1).

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

Данная последовательность коллапсов я = [i (1),... я (m)] приводит к значению, которое имеет нижнюю границу, равную сумме d (i (m)) для всех m от 1 до пк.

Нам нужно доказать, что не может быть последовательности, отличной от той, которая была создана алгоритмом с меньшим diff. Итак, пусть приведенная выше последовательность будет той, что вытекает из алгоритма. Пусть J = [j (1),... j (m)].

Здесь он становится скудным: Я думаю, что должно быть возможно доказать, что нижний предел J больше фактического значения I, потому что на каждом шаге мы выбираем по конструкции операцию коллапса из I, поэтому он должен быть меньше, чем совпадение коллапса из альтернативной последовательности

Я думаю, мы могли бы предположить, что последовательности являются дизъюнктными, но я не совсем уверен в этом.

Ответ 6

Вот алгоритм грубой силы, написанный на Python, который, похоже, работает.

from itertools import combinations
def get_best_order(n, k):
    slices = combinations(range(1, len(n)), k-1)
    container_slices = ([0] + list(s) + [len(n)] for s in slices)
    min_value = -1
    best = None
    def get_value(slices, n):
        value = 0
        for i in range(1, len(slices)):
            start, end = slices[i-1], slices[i]
            num_red = len([b for b in n[start:end] if b == 'r'])
            value += num_red * (end - start - num_red)
        return value
    for slices in container_slices:
        value = get_value(slices, n)
        if value < min_value or min_value == -1:
            min_value = value
            best = slices
    return [n[best[i-1]:best[i]] for i in range(1, len(best))]
n = ['b', 'r', 'b', 'r', 'r', 'r', 'b', 'b', 'r']
k = 4
print(get_best_order(n, k))
# [['b', 'r', 'b'], ['r', 'r', 'r'], ['b', 'b'], ['r']]

В основном алгоритм работает следующим образом:

• Создайте список всех возможных расположений (элементы остаются в порядке, так что это всего лишь количество элементов на контейнер)
• Рассчитайте значение для этой схемы, как описано OP
• Если это значение меньше текущего наилучшего значения, сохраните его
• Возвращает расположение, имеющее самое низкое значение