@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 91i 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 at http://groups.google.com/group/algogeeks?hl=en.
