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 <[email protected]> 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 <[email protected]> wrote:
> > @DufusCan u pls give the algorithm about how to do this?
> >
> >
> >
> > On Fri, Aug 14, 2009 at 8:56 PM, Dufus <[email protected]>
> 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 <[email protected]> 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 [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
-~----------~----~----~----~------~----~------~--~---
