问题 Google Combinatorial Optimization面试问题

我认为我们可以使用动态编程来解决这个问题。

基本上，我们有：

F（I，J） 定义为从大小数组中选择的所有预期值的最大总和 一世  分裂成 Ĵ 子阵。因此解决方案应该是 F（N，k）的。

递归方程是：

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

我不知道是否有人仍然有兴趣看到这个问题的解决方案。半小时前偶然发现了这个问题并考虑发布我的解决方案（Java）。其复杂性为O（n * K ^ log10）。证明有点复杂，所以我宁愿提供运行时编号：

n k时间（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;
}
 }

不确定我理解，算法是将数组分组，对吧？总和可以具有的最大值是1的数量。因此，将数组拆分为每个1个元素的“n”组，并且加法将是可能的最大值。但它必须是别的东西，我不明白这个问题，这似乎太傻了。

我认为这可以通过动态编程来解决。在每个可能的拆分位置，如果您在该位置拆分，并且在该点没有拆分，则获取最大总和。递归函数和存储历史的表可能很有用。

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)
           }

这可能导致一些事情......

我认为这是一个糟糕的面试问题，但它也是一个容易解决的问题。

每个整数都会产生重量为1 / s的预期值，其中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. 创建一个分区，其中包含最大数量的最大大小数组和最小数量的最小大小数组
2. 从1的最小值开始填充数组
3. 用0表示填充剩余的插槽

递归函数怎么样：

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）计算从1到m的A的分裂的期望值，即（A [1] + A [l + 1] + ... A [m]）/（ M-L + 1）。

在计算ceil（n / 2k）和floor（3n / 2k）之间的有效分割大小数组后，BestValue调用BestValueHelper。

我省略了错误处理和一些结束条件，但这些不应该太难添加。

让

• a [] =给定长度为n的数组
• from =包含数组a的索引
• k =所需拆分的数量
• minSize =拆分的最小尺寸
• maxSize =拆分的最大大小
• d = maxSize - minSize

• expectation（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）