@divya : descending order sorting works. BRILLIANT !! 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 Bombay http://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 at http://groups.google.com/group/algogeeks?hl=en.
