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]> >> > >> >> . >> >> 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. > >
-- -------------------------------------------------- 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.
