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