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>
>> .
>> 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.
>
>
--
--------------------------------------------------
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
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.
