One more way to do this can be:
1. sorting the number in decreasing order
2. start with 2 empty sets A and B and assign first 2 elements to each of
them (see the following example)
3. maintain the sums of A and B in variables.
4. take the next number from list and add it to the set where the sum is
less than the other and update the sum
5. similarly add the rest of the numbers.
6. Now in case one set contains less number of elements than other, then
add the last |size(A)-size(B)|/2 elements from the set with more size to the
one with less size
Example:
list: {1,2,3,4,5,6,7,23}
set: A={}, B={}
sumA=0, sumB=0
sort list in descending order: list:{23,7,6,5,4,3,2,1}
add first 2 elements 2 each set
A={23}, sumA=23 and B={7}, sumB=7
take next element '6'
since sumB<sumA add it to set B
A={23}, sumA=23 and B={7,6}, sumB=7+6=13
take next element '5'
since sumB<sumA add it to set B
A={23} sumA=23 and B={7,6,5}, sumB=7+6+5=18
take next element '4'
since sumB<sumA add it to set B
A={23}, sumA=23 and B={7,6,5,4}, sumB=7+6+5+4=22
take next element '3'
since sumB<sumA add it to set B
A={23}, sumA=23 and B={7,6,5,4,3}, sumB=7+6+5+4+3=25
take next element '2'
since sumA<sumB add it to set B
A={23,2}, sumA=23+2=25 and B={7,6,5,4,3}, sumB=7+6+5+4+3=25
take next element '1'
select any one set in case of equality (let it be A in this case)
A={23,2,1}, sumA=23+2+1=26 and B={7,6,5,4,3}, sumB=7+6+5+4+3=25
now size(A)=3 and size(B)=5, so add the last |5-3|/2 (=1) element from B to
A and we get
A={23,2,1,3} and B={7,6,5,4}
and difference of sums=29-22=7
Let me know if theres something wrong with this approach.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Fri, May 14, 2010 at 1:51 PM, 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
>
> --
> 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.
