On May 17, 5:36 pm, Rohit Saraf <[email protected]> wrote: > @divya : descending order sorting works. BRILLIANT !!
Not really. Try this input: 8 6 5 5 5 1 The best partition is [8 6 1] [5 5 5] but Divya's algorithm gives [8 5 1] [6 5 5]. -Jagadish http://www.cse.iitb.ac.in/~jagadish > On 5/17/10, divya jain <[email protected]> wrote: > > > > > my algo on the array 1 200 500 2000 > > sort the array therefore we have now 2000 500 200 1 > > 1st array will have largest element > > A= {2000} > > and B={500} > > sumA=2000 > > sumB=500 > > now abs((2000+200)-500)>abs((2000)-(500+200)) > > so we ll put 200 in array B. now since B has n/2 elements rest of the > > element goes to array which is 1. > > so the ans is > > A={2000,1} > > b={500,200} > > > On 15 May 2010 19:10, Rohit Saraf <[email protected]> wrote: > > >> so what will ur algo give for array 1,200,500,2000 > > >> On 5/15/10, divya jain <[email protected]> wrote: > >> > my approach: > >> > 1. sort the array > >> > 2. take a variable diff. intitialize it to 0. > >> > 3. take the 1st element from array nd place it in array A and 2nd > >> > element > >> in > >> > array B. stoe in diff sum(A)-sum(B). > >> > 4. now place the next element in array A or B according to the condition > >> if > >> > if sum(A+element)-sum(B)> sum(a)-sum(B+element). store the > >> > element > >> in > >> > B otherwise in A. also while storing the element in ny array maintain > >> the > >> > count of element in that aaray. if any time the count reaches n/2 where > >> > n > >> is > >> > the no. of elements in the given aaray. then store rest element in the > >> > other array. > >> > 5. repeat step 5 until both array A n B get n/2 elements.. > > >> > hope my approach is clear and correct. > >> > comments are welcomed..... > > >> > On 15 May 2010 08:47, Rohit Saraf <[email protected]> wrote: > > >> >> Choosing a greedy strategy for this would be difficult. > > >> >> For a simple dp you can > >> >> maintain A[i,total,present] using a recurrence > > >> >> i is the present index of array > >> >> total is the number of elements reqd in first partition. > >> >> present is the no of elements already there in first partition. > > >> >> the array stores difference between sums. GET the minimum of all these > >> >> and backtrack. > > >> >> On 5/15/10, Amir hossein Shahriari <[email protected]> > >> >> wrote: > >> >> > @karas: your solution is greedy and its wrong e.g. for > >> >> > {1,2,3,4,5,100} > >> >> your > >> >> > diff would be 95 but the best result is 91 > > >> >> > i think we can solve this problem by dynamic programming but not a > >> >> > simple > >> >> > one! since the size of the two subsets must be equal. > >> >> > so it's DP solution has at least 3 dimensions: tow dimensions > >> >> representing > >> >> > the number of elements in each subset and another for the difference > >> >> between > >> >> > their sums > > >> >> > On Fri, May 14, 2010 at 10:11 PM, W Karas <[email protected]> wrote: > > >> >> >> On May 14, 4:51 am, divya <[email protected]> wrote: > >> >> >> > Algorithm to partition set of numbers into two s.t. diff bw their > >> >> >> > sum is min and they hav equal num of elements > > >> >> >> void part(const int a[], int n_a, int g1[], int g2[]) > >> >> >> { > >> >> >> int i, j, k; > > >> >> >> /* diff = sum(g1) - sum(g2) */ > >> >> >> int diff; > > >> >> >> sort(a, n_a); > > >> >> >> diff = 0; > >> >> >> for (i = 0, j = 1, k = 0; j < n_a; ++k, i += 2, j += 2) > >> >> >> { > >> >> >> if ((a[i] > a[j]) == (diff > 0)) > >> >> >> { > >> >> >> g1[k] = a[j]; > >> >> >> g2[k] = a[i]; > >> >> >> } > >> >> >> else > >> >> >> { > >> >> >> g1[k] = a[i]; > >> >> >> g2[k] = a[j]; > >> >> >> } > >> >> >> diff += g1[k] - g2[k]; > >> >> >> } > >> >> >> } > > >> >> >> -- > >> >> >> 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]<algogeeks%[email protected]> > >> <algogeeks%[email protected]<algogeeks%[email protected]> > > >> >> <algogeeks%[email protected]<algogeeks%[email protected]> > >> <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]> > >> <algogeeks%[email protected]<algogeeks%[email protected]> > > >> >> . > >> >> > For more options, visit this group at > >> >> >http://groups.google.com/group/algogeeks?hl=en. > > >> >> -- > >> >> -------------------------------------------------- > >> >> Rohit Saraf > >> >> Second Year Undergraduate, > >> >> Dept. of Computer Science and Engineering > >> >> IIT Bombay > >> >>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > >> <http://www.cse.iitb.ac.in/%7Erohitfeb14> > > >> >> -- > >> >> 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]<algogeeks%[email protected]> > >> <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]> > >> . > >> > For more options, visit this group at > >> >http://groups.google.com/group/algogeeks?hl=en. > > >> -- > >> -------------------------------------------------- > >> Rohit Saraf > >> Second Year Undergraduate, > >> Dept. of Computer Science and Engineering > >> IIT Bombay > >>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > >> -- > >> 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]<algogeeks%[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. > > -- > Sent from my mobile device > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 > > -- > 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 > athttp://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.
