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 <[email protected]>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 [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.
