Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh <sourabhd2...@gmail.com> wrote: > 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 <sourabhd2...@gmail.com> wrote: > > Because in the previous example k = 3. > > > > On Nov 27, 10:46 pm, Piyush Grover <piyush4u.iit...@gmail.com> 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 <ankurga...@gmail.com> > 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 algogeeks@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com. > > > > 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.