How about:
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 = n_a - 1, k = 0; i < j; ++k, ++i, --j)
{
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];
}
}
On May 14, 2:30 pm, 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]>
> > .
> > 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.
