use dynamic programming.
Make this problem similar to knapsack one.
You want to find the items from a given array which sums up to (exactly or
nearly) S/2 (here S is total sum of all integers)
Let's say
P(i,j) is probability to make a sum = j with the first i items in the array.
P(i,j) = 1 if P(i-1,j) ==1 || P(i-1,j-a[i]) == 1 else 0
So you can rewrite it as
P(i,j) = max { P(i-1,j) , P(i-1,j-a[i]) }
you would like to calculate values of P
from i=1, j=1 to i=size_of_array , j = S/2
then find the max value of j for which value of P is 1. time complexity will
be O(nS) and same is the space complexity
That's it.
On Wed, Dec 29, 2010 at 10:37 PM, Ankur Khurana <ankur.kkhur...@gmail.com>wrote:
> How will you divide and array of approx 100 elements into two sub sets
> of 50 each such that the difference between both the subsets is the
> minimum possible one . .
>
> Thanks in advance .
> Ankur
>
> --
> 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.
