I was really not able to digest the greedy thing.... Great example!! On 5/17/10, Amir hossein Shahriari <[email protected]> wrote: > @divya : it's a greedy approach and again it's WRONG! > your answer for {110,100,90,70,60,10 } would be: > A = { 110, 70, 60 } > B = { 100, 90 , 10 } > the difference is 40 > the correct ans: > A = { 110, 100 , 10 } > B = { 90 , 70 , 60 } > the difference is 0 > i don't believe a greedy algorithm would work for this problem! > > On Mon, May 17, 2010 at 5:06 PM, Rohit Saraf > <[email protected]>wrote: > >> @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]> >> > >> >> > >> >> >> <algogeeks%[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]> >> > >> >> <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. >> >> >> > >> >> >> > >> >> >> >> >> >> >> >> >> -- >> >> >> -------------------------------------------------- >> >> >> 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> >> >> <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]> >> > >> >> <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. >> > >> > >> >> -- >> 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<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.
