Your solution does not consider the fact that the two subsets have equal elements(50 elements each) You have provided a solution for http://www.spoj.pl/problems/FCANDY/ But this question is different. It is similar to http://www.codechef.com/problems/TEAMSEL/
On Dec 29, 10:56 pm, vishal raja <[email protected]> wrote: > 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%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 [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.
