Разбейте массив на порядок

Question

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

Вопрос:

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

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

Как вы решаете это?Пока что у меня есть только тривиальные случаи, когда

• , если (n == k), ответ будет нулевым, потому что вы можете просто поместить один в каждый контейнер, делая значение каждого контейнера нулевымследовательно, сумма будет равна нулю.
• если (k == 1), вы просто выбросите все из них и вычислите произведение.
• если присутствует только один цвет, ответ будет нулевым.

Редактировать :

Я приведу пример.

n = 4 и k = 2

Ввод: RBRR

Первый контейнер получает первые два (R и B), делающие его значение 1 (1R X 1B) Второй контейнер получает оставшиеся (R и R), делая его значение 0 (2R x 0B).ответ: 1 + 0 = 1

, если k = 3, у первого контейнера будет только первая кнопка (R), у второго контейнера будет только вторая (B), у третьего - последние двакнопки (R и R) Каждый из контейнеров будет иметь значение 0 и, следовательно, сумма и ответ будут равны 0.

Надеюсь, это прояснит сомнения.

Answer 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) с помощью определенных предварительных вычислений ( подсказка : использовать dp[i][1]).Я опубликую это завтра, если никто не поймет, что это на самом деле неправильно до тех пор.

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

Answer 2

Предупреждение: доказано, что оно неоптимально

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

В этом решении мы используем 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

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

Контрпример: Спасибо Жюлю Оллеону за предоставленный контрпример, о котором мне было лень думать:

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 *, для улучшения времени выполнения исчерпывающего поиска, но это не приведет к полиномиальному времени выполнения.

Answer 3

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

Answer 4

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

Answer 5

Вот алгоритм грубой силы, написанный на 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
• Если это значение меньше текущего наилучшего значения,сохранить его
• Вернуть договоренность с наименьшим значением

Answer 6

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

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

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

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

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

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

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

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

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

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

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

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

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