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