@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 wrote:
> This can be solved in single dimension itself
>
> like this
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=0 && j >=a[i]; j-- )
DP[j] = DP[j-a[i]];
for( j = m ; j>=0 ; j--)
if(DP[j]) break;
so the a
Thanks a lot.
Its a real good explanation of the algorithm.
Nikhil Jindal
On Sat, Aug 15, 2009 at 1:02 PM, Dufus 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 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 wrote:
> @DufusCan u pls give the algorithm about how to do this?
>
>
>
> On Fri, Aug 14, 2009 at 8:56 PM, Dufus wrote:
>
> > If the range is giv
@DufusCan u pls give the algorithm about how to do this?
On Fri, Aug 14, 2009 at 8:56 PM, Dufus 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
Yup, NP-complete.
Read this if you like: http://arxiv.org/ftp/cond-mat/papers/0310/0310317.pdf
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@g
knapsack problem
On Fri, Aug 14, 2009 at 7:10 PM, fundoonick wrote:
> The modulus(or absolute) of difference should be minimum.Or the difference
> should be closest to 0(-ve or +ve side).
>
> For ex, for 5,6,7,8,9
> Required sets are: {5,6,7} and {8,9}
> The difference is abs((5+6+7)-(8+9)) = 1
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 wrote:
> P
The modulus(or absolute) of difference should be minimum.Or the difference
should be closest to 0(-ve or +ve side).
For ex, for 5,6,7,8,9
Required sets are: {5,6,7} and {8,9}
The difference is abs((5+6+7)-(8+9)) = 1
Hope it clears your doubt
Nikhil Jindal
On Fri, Aug 14, 2009 at 7:02 PM, Ajinky
NP-COMPLETE
2009/8/14 fundoonick
> 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
sorry i meant >=0 .. or are negative differences allowed ?
On Fri, Aug 14, 2009 at 7:02 PM, Ajinkya Kale wrote:
> Should the difference be <= 0 always ?
>
>
> On Fri, Aug 14, 2009 at 6:57 PM, fundoonick wrote:
>
>> Problem:
>> I have a set of positive integers. I have to divide it into 2 sets su
Should the difference be <= 0 always ?
On Fri, Aug 14, 2009 at 6:57 PM, fundoonick 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
12 matches
Mail list logo
