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

Question

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

Вопрос:

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

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

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

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

Edit:

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

п = 4 и к = 2

Входной сигнал: RBRR

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

В этом решении мы используем G для обозначения количества смежных областей одного цвета в последовательности кнопок. Скажем, мы (я использую х для красного и синего 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 < = к, то есть, как минимум, равный нулю, так как каждая группировка может пойти в свой собственный контейнер. Предположим теперь, что 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 

И к = 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 

к = 3

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

к = 2

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

к = 1

6/5 //total value: 30 

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

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

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

Если к = 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 4

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 5

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