Looks like a dynamic programming problem....
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) <= r <= floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) <= N
<= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh <[email protected]> wrote:
> Because in the previous example k = 3.
>
> On Nov 27, 10:46 pm, Piyush Grover <[email protected]> wrote:
>
>
>
>
>
>
>
> > Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
> > Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
> > why this is not the optimal split???
>
> > On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg <[email protected]> wrote:
> > > You have an array with *n* elements. The elements are either 0 or 1. You
> > > want to *split the array into kcontiguous subarrays*. The size of each
> > > subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
> > > k << n. After you split the array into k subarrays. One element of each
> > > subarray will be randomly selected.
>
> > > Devise an algorithm for maximizing the sum of the randomly selected
> > > elements from the k subarrays. Basically means that we will want to split
> > > the array in such way such that the sum of all the expected values for the
> > > elements selected from each subarray is maximum.
>
> > > You can assume that n is a power of 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
>
> > > Source ->
> > > http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
