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