@Arun Elegant! I see it like a reduction of Integer partition problem to Knapsack problem. Where:- The target is SUM_OF_GIVEN_INTEGERS/2 and we want to get as close to the target as possible.
_dufus On Aug 15, 8:31 pm, Arun N <arunn3...@gmail.com> wrote: > This can be solved in single dimension itself > > like this > > SUM = sum of elements > m = SUM/2 > > DP[0] =1; // DP[ i ] = 1 if it is possible to reach sum ' i ' using the > elements > > for ( i=0 ; i<n ; i++ ) > for ( j = m ; j>=0 && j >=a[i]; j-- ) > DP[j] = DP[j-a[i]]; > > for( j = m ; j>=0 ; j--) > if(DP[j]) break; > > so the answer is > > j and SUM - j > > Arun, > > > > On Sat, Aug 15, 2009 at 1:02 PM, Dufus <rahul.dev.si...@gmail.com> wrote: > > > Plz refer to > > Balanced Partition Problem or > > Integer Partition Problem at > > >http://people.csail.mit.edu/bdean/6.046/dp/ > > > On Aug 14, 10:26 pm, fundoonick <fundoon...@yahoo.co.in> wrote: > > > @DufusCan u pls give the algorithm about how to do this? > > > > On Fri, Aug 14, 2009 at 8:56 PM, Dufus <rahul.dev.si...@gmail.com> > > wrote: > > > > > If the range is given then it get reduced to a standard problem which > > > > can be solved by DP in O(k.n^2) time..where n integers within range > > > > 0...K have to be partitioned in two sets S1 and S2 such that the > > > > difference of sum of their elements is min. > > > > > _dufus > > > > > On Aug 14, 6:27 pm, fundoonick <fundoon...@yahoo.co.in> wrote: > > > > > Problem: > > > > > I have a set of positive integers. I have to divide it into 2 sets > > such > > > > that > > > > > the difference of the sums of both sets is minimum. > > > > > For ex, the given set of +ve integers is: 1,2,3,4 > > > > > I divide it into 2 sets {1,4} and {2,3} such that the difference of > > their > > > > > sum (1+4=)5 - (2+3=)5 = 0 > > > > > This is the least possible difference. > > > > > > Pls help. > > -- > Potential is not what U have, its what U think U have!!! > It is better to worn out than rust. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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 -~----------~----~----~----~------~----~------~--~---
