Try this .. i think it will work.. correct me if wrong
sort(&x[0],&x[n]);
ysum=y[0]=x[n-1];
ysum=z[0]=x[n-2];
j=0;
k=n-3;
l=n/2;
for(i=1;i<l;i++){
if(ysum<zsum){
ysum+=x[k];
zsum+=x[j];
y[i]=x[k];
z[i]=x[j];
}else{
ysum+=x[j];
zsum+=x[k];
y[i]=x[j];
z[i]=x[k];
}
j++;
k--;
}
On May 17, 4:14 pm, 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]>
>
> > >> >> .
> > >> >> 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.
>
> > --
> > --------------------------------------------------
> > 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
> athttp://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.
