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 <rohit.kumar.sa...@gmail.com> wrote:
> so what will ur algo give for array 1,200,500,2000
>
> On 5/15/10, divya jain <sweetdivya....@gmail.com> 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 <rohit.kumar.sa...@gmail.com> 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 <amir.hossein.shahri...@gmail.com>
> >> 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 <wka...@yahoo.com> wrote:
> >> >
> >> >> On May 14, 4:51 am, divya <sweetdivya....@gmail.com> 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 algoge...@googlegroups.com.
> >> >> To unsubscribe from this group, send email to
> >> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> >
> >> >> .
> >> >> 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 algoge...@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> .
> >> > 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 algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> .
> >> 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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> > 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
