algorithm - 谷歌组合优化面试题

Question

几周前我在谷歌的面试中被问到这个问题，我没有完全得到答案，我想知道这里是否有人可以帮助我。

您有一个包含 n 个元素的数组。元素为 0 或 1。您想要将数组拆分成 k 个连续个子数组。每个子数组的大小可以在 ceil(n/2k) 和 floor(3n/2k) 之间变化。您可以假设 k << n。将数组拆分为 k 个子数组后。每个子数组的一个元素将被随机选择。

设计一种算法，使从 k 个子数组中随机选择的元素的总和最大化。基本上意味着我们希望以这样的方式拆分数组，使得从每个子数组中选择的元素的所有期望值的总和最大。

你可以假设 n 是 2 的幂。

Example:

Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6

Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.4333333 

Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.83333333

Answer 1

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

基本上，我们有:

f(i,j) is defined as the maximum sum of all expected values chosen from an array of size i and split into j subarrays. Therefore the solution should be f(n,k).

递归方程为:

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