Re: [algogeeks] Re: partitioning the array
yes we would use 2 dimensional array to store the values inbetween but the main question here is that is the reccurence realation correct?? On Mon, May 9, 2011 at 11:31 AM, anshu anshumishra6...@gmail.com wrote: @gaurav both things are same, matrix is a simple and efficient way to do problem like this. . -- 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. -- Gaurav Aggarwal SCJP -- 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.
Re: [algogeeks] Re: partitioning the array
@gaurav
f(i, j) = {(total number we need to make sum j including ith number in
array), if its not possible than -1};
f(i, j) = f(i-1, j-ar[i]) + 1 -- if (i-1, j-ar[i]) != -1;
answer will be the largest j for which f(i, j) will be exactly equals to
n/2;
there is something more in this but when you start to write the code you can
easily get that.
https://www.spoj.pl/problems/AMR10D/ a little bit similar problem on spoj.
--
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.
Re: [algogeeks] Re: partitioning the array
@anshu then shall we use the foll reccurence realation?? 1i=n S=(s+1)/2 f(i,S)= min( f(i-1, S), f(i-1, S- ar[i]) ) On Mon, May 9, 2011 at 10:42 AM, anshu anshumishra6...@gmail.com wrote: Use KnapSack DP. suppose the sum of element = s and number of elements = n make a 2-dimesnsional array of size n * ((s+1)/2); I think that much hint is enough. if we think little bit more we can optimize it also. -- 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. -- Gaurav Aggarwal SCJP -- 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.
Re: [algogeeks] Re: partitioning the array
@cegprakash: it doesnt ensure that both the arrays will be having same number of elements On Sat, May 7, 2011 at 10:10 PM, cegprakash cegprak...@gmail.com wrote: simple.. sum all the n elements.. a= floor(sum/2) b=sum-a output is a b -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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.
Re: [algogeeks] Re: partitioning the array
sorry, i misunderstood the problem statement On Sun, May 8, 2011 at 10:53 AM, Aakash Johari aakashj@gmail.comwrote: @cegprakash: it doesnt ensure that both the arrays will be having same number of elements On Sat, May 7, 2011 at 10:10 PM, cegprakash cegprak...@gmail.com wrote: simple.. sum all the n elements.. a= floor(sum/2) b=sum-a output is a b -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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.
