Проблема собеседования с комбинаторной оптимизацией Google

Ответ 1

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

Вот основное решение O (n ^ 2 * k), которое должно быть адекватным для малых k (как указал интервьюер):

def best_val(arr, K):
  n = len(arr)
  psum = [ 0.0 ]
  for x in arr:
    psum.append(psum[-1] + x)
  tab = [ -100000 for i in range(n) ]
  tab.append(0)
  for k in range(K):
    for s in range(n - (k+1) * ceil(n/(2*K))):
      terms = range(s + ceil(n/(2*K)), min(s + floor((3*n)/(2*K)) + 1, n+1))
      tab[s] = max( [ (psum[t] - psum[s]) / (t - s) + tab[t] for t in terms ])
  return tab[0]

Я использовал функции numpy ceil/floor, но вы в основном поняли эту идею. Единственные "трюки" в этой версии - это то, что он делает окна, чтобы уменьшить накладные расходы памяти только на O (n) вместо O (n * k) и что он предварительно вычисляет частичные суммы, чтобы вычислить ожидаемое значение для поля a (таким образом, сохраняя коэффициент O (n) от внутреннего цикла).

Ответ 2

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

В принципе, мы имеем:

f (i, j) определяется как максимальная сумма всех ожидаемых значений, выбранных из массива размера i, и разбивается на j subarrays. Поэтому решение должно быть f (n, k).

Рекурсивное уравнение:

f(i,j) = f(i-x,j-1) + sum(i-x+1,i)/x where (n/2k) <= x <= (3n/2k)

Ответ 3

Я не знаю, хочет ли кто-нибудь еще увидеть решение этой проблемы. Только наткнулся на этот вопрос полчаса назад и подумал о публикации моего решения (Java). Сложностью для этого является O (n * K ^ log10). Доказательство немного свернуто, поэтому я бы предпочел предоставить номера времени выполнения:

n k time (ms)
48 4 25
48 8 265
24 4 20
24 8 33
96 4 51
192 4 143
192 8 343919

Решение является тем же самым старым рекурсивным, когда задан массив, выберите первый раздел размера ceil (n/2k) и найдите наилучшее решение рекурсивно для остальных с числом разделов = k -1, затем возьмите ceil ( n/2k) + 1 и т.д.

код:

public class PartitionOptimization {
public static void main(String[] args) {
    PartitionOptimization p = new PartitionOptimization();
    int[] input = { 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0};
    int splitNum = 3;
    int lowerLim = (int) Math.ceil(input.length / (2.0 * splitNum));        
    int upperLim = (int) Math.floor((3.0 * input.length) / (2.0 * splitNum));
    System.out.println(input.length + " " + lowerLim + " " + upperLim + " " +
            splitNum);
    Date currDate = new Date();
    System.out.println(currDate);       
    System.out.println(p.getMaxPartExpt(input, lowerLim, upperLim,
            splitNum, 0));
    System.out.println(new Date().getTime() - currDate.getTime());
}

public double getMaxPartExpt(int[] input, int lowerLim, int upperLim,
        int splitNum, int startIndex) {
    if (splitNum <= 1 && startIndex<=(input.length -lowerLim+1)){
        double expt = findExpectation(input, startIndex, input.length-1);           
        return expt;
    }
    if (!((input.length - startIndex) / lowerLim >= splitNum))
        return -1;
    double maxExpt = 0;
    double curMax = 0;
    int bestI=0;
    for (int i = startIndex + lowerLim - 1; i < Math.min(startIndex
            + upperLim, input.length); i++) {
        double curExpect = findExpectation(input, startIndex, i);           
        double splitExpect = getMaxPartExpt(input, lowerLim, upperLim,
                splitNum - 1, i + 1);
        if (splitExpect>=0 && (curExpect + splitExpect > maxExpt)){
            bestI = i;
            curMax = curExpect;
            maxExpt = curExpect + splitExpect;
        }
    }
    return maxExpt;
}

public double findExpectation(int[] input, int startIndex, int endIndex) {
    double expectation = 0;
    for (int i = startIndex; i <= endIndex; i++) {
        expectation = expectation + input[i];
    }
    expectation = (expectation / (endIndex - startIndex + 1));
    return expectation;
}
 }

Ответ 4

Не уверен, что я понимаю, алгоритм состоит в том, чтобы разбить массив на группы, правильно? Максимальное значение, которое может иметь сумма, - это количество единиц. Так разбивайте массив в "n" группах по 1 элемента каждый, и добавление будет максимально возможным. Но это должно быть что-то еще, и я не понял проблему, это кажется слишком глупым.

Ответ 5

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

sum_i = max{ NumOnesNewPart/NumZerosNewPart * sum(NewPart) + sum(A_i+1, A_end),
                sum(A_0,A_i+1) + sum(A_i+1, A_end)
           }

Это может привести к чему-то...

Ответ 6

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

Каждое целое число вносит вклад в ожидаемое значение с весом 1/с, где s - размер набора, где он был помещен. Поэтому, если вы угадываете размеры наборов в своем разделе, вам просто нужно заполнить наборы теми, которые начинаются с самого маленького набора, а затем заполнить оставшийся наибольший набор нулями.

Вы можете легко видеть, что если у вас есть раздел, заполненный, как указано выше, где размеры наборов S_1,..., S_k, и вы делаете преобразование, в котором вы удаляете один элемент из набора S_i и переместите его на установите S_i + 1, у вас есть следующие случаи:

• Оба S_i и S_i + 1 были заполнены единицами; то ожидаемое значение не изменяется
• Оба они были заполнены нулями; то ожидаемое значение не изменяется
• S_i содержит как 1, так и 0, а S_i + 1 содержит только нули; перемещение 0 в S_i + 1 увеличивает ожидаемое значение, так как ожидаемое значение S_i увеличивается
• S_i содержит 1 и S_i + 1 содержит как 1, так и 0; перемещение 1 в S_i + 1 увеличивает ожидаемое значение, так как ожидаемое значение S_i + 1 увеличивается, а S_i остается неизменным.

Во всех этих случаях вы можете перенести элемент из S_i в S_i + 1, сохраняя правило заполнения заполняющих наименьших множеств с 1, чтобы ожидаемое значение возрастало. Это приводит к простому алгоритму:

• Создайте разбиение на разделы, где максимальное количество массивов максимального размера и максимальное количество массивов минимального размера
• Заполните массивы, начиная с самого маленького с помощью 1
• Заполните оставшиеся слоты 0

Ответ 7

Как насчет рекурсивной функции:

int BestValue(Array A, int numSplits)
// Returns the best value that would be obtained by splitting 
// into numSplits partitions.

Это, в свою очередь, использует хелпер:

// The additional argument is an array of the valid split sizes which 
// is the same for each call.
int BestValueHelper(Array A, int numSplits, Array splitSizes)
{
    int result = 0;
    for splitSize in splitSizes
        int splitResult = ExpectedValue(A, 0, splitSize) + 
                          BestValueHelper(A+splitSize, numSplits-1, splitSizes);
        if splitResult > result
            result = splitResult;
}

ExpectedValue (Array A, int l, int m) вычисляет ожидаемое значение раскола A, которое переходит от l к m, т.е. (A [l] + A [l + 1] +... A [m] )/(m-l + 1).

BestValue вызывает BestValueHelper после вычисления массива допустимых разделенных размеров между ceil (n/2k) и floor (3n/2k).

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

Ответ 8

Пусть

• a [] = заданный массив длины n
• from = инклюзивный индекс массива a
• k = количество требуемых расщеплений
• minSize = минимальный размер раскола
• maxSize = максимальный размер раскола
• d = maxSize - minSize

• Ожидание (a, from, to) = среднее значение для всех элементов массива a от "from" до "to"

  Optimal(a[], from, k) = MAX[ for(j>=minSize-1 to <=maxSize-1) { expectation(a, from, from+j) + Optimal(a, j+1, k-1)} ]
  

Время выполнения (при условии memoization или dp) = O (n * k * d)