What if we sort array and place first n/4 and last n/4 elements in one subarray and other n/2 in the 2nd subarray.
On Fri, Dec 31, 2010 at 4:08 AM, Anand <anandut2...@gmail.com> wrote: > http://anandtechblog.blogspot.com/2010/07/partition-of-array.html > > > On Thu, Dec 30, 2010 at 12:35 AM, vishal raja <vishal.ge...@gmail.com>wrote: > >> This means , You can make a sum = j , with or without using the item i , >> while calculating P[i][j]. >> >> So you can have another counter Count2 which will have the count for such >> items. So you will calculate P as discussed before >> but You will add 1 in Count2[i][j] whenever you find that case. add one in >> count[i][j] in any of P = 1 case. >> >> in the end you'll search for the max value of j (closest to S/2) for all P >> values which has this property on value of i . >> 1. i = 50 >> 2. for all i> 50 >> i-count2[i][j] <= 50 >> >> I think this will do. Check it out. >> On Thu, Dec 30, 2010 at 12:41 PM, Ankur Khurana <ankur.kkhur...@gmail.com >> > wrote: >> >>> vishal , what will we do to count when both p[i-1][j] and >>> p[i-1][j-a[i]] is true . >>> >>> On Thu, Dec 30, 2010 at 12:36 PM, Ankur Khurana >>> <ankur.kkhur...@gmail.com> wrote: >>> > Thanks everybody for wonderful support and special thanks to Vishal >>> > raja. . But i was bit apprehensive about your last solution . . i will >>> > test it :) and let you know as well . Thanks . . . . >>> > >>> > >>> > On Thu, Dec 30, 2010 at 11:52 AM, vishal raja <vishal.ge...@gmail.com> >>> wrote: >>> >> But the same solution I've given above can give you the solution for >>> this >>> >> problem . >>> >> In the formed table of P[i][j] , you can take another variable >>> attached to >>> >> it as count[i][j] for how many items we have selected yet. >>> >> So you gotta find , the max. value of j which has count = 50. >>> >> count[i][j] = count[i-1][j] if P(i-1,j) ==1 >>> >> count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 >>> >> else count[i][j] = 0 >>> >> >>> >> >>> >> >>> >> >>> >> On Thu, Dec 30, 2010 at 11:42 AM, vishal raja <vishal.ge...@gmail.com >>> > >>> >> wrote: >>> >>> >>> >>> yeah, My bad. >>> >>> Missed that. >>> >>> >>> >>> On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares < >>> wladimir...@gmail.com> >>> >>> wrote: >>> >>>> >>> >>>> Sum up all the number and divide by 2 >>> >>>> >>> >>>> Using the algorithm subset problem to find a number close to median >>> >>>> >>> >>>> >>> >>>> Wladimir Araujo Tavares >>> >>>> Federal University of Ceará >>> >>>> >>> >>>> >>> >>>> >>> >>>> >>> >>>> >>> >>>> >>> >>>> On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana < >>> ankur.kkhur...@gmail.com> >>> >>>> wrote: >>> >>>>> >>> >>>>> How will you divide and array of approx 100 elements into two sub >>> sets >>> >>>>> of 50 each such that the difference between both the subsets is the >>> >>>>> minimum possible one . . >>> >>>>> >>> >>>>> Thanks in advance . >>> >>>>> Ankur >>> >>>>> >>> >>>>> -- >>> >>>>> You received this message because you are subscribed to the Google >>> >>>>> Groups "Algorithm Geeks" group. >>> >>>>> To post to this group, send email to algoge...@googlegroups.com. >>> >>>>> To unsubscribe from this group, send email to >>> >>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>> >>>> To unsubscribe from this group, send email to >>> >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>> >> To unsubscribe from this group, send email to >>> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
