Page 1 of 1

Challenge in a DP problem

Posted: Thu Mar 08, 2007 3:51 pm
by 7erry
Let's come to this problem:
there's a set A={x1,x2,...,xn}. Our goal is dividing the set into 2 groups in order to the difference between sum of all the elements in group 1 and sum of all elements in group 2 is smallest

this is a typical problem using DP, the array's size for DP is |max{x1,x2,..,xn}-min{x1,x2,...,xn}|. So I wonder if there is another DP problem which is not depending on the elements' bound (as you see, if max of the elements is 10^12, the problems cannot be solved in any traditional ways)

Posted: Sun Nov 25, 2007 4:20 am
by ericschmidt
Hey 7erry!

I've just came across your posting and although I don't know much about DP I was wondering if you have also thought about a second way of looking at your problem. The eqivalent problem is to pick a subset B out of the set A={x1,x2,...,xn} where the sum of all elements of B is "closest" to 0.5*sum(x1,x2,...,xn)

So at least you know exactly where your "goal" is ...

It still remains a "puzzle laying kind of problem" ... of course.

Posted: Sun Nov 25, 2007 12:41 pm
by fpavetic

Posted: Mon Nov 26, 2007 11:00 pm
by ericschmidt
Hi fpavetic!

It took me a while to understand ... but now I really can see the brilliance in the exponential time algorithm for the subset sum problem (from Horowitz and Sahni). Thanks for that link to wikipedia.

My first own idea was to split the set A into two sets (A1 and A2) with A1 holding the "smaller" values and A2 the "larger" ones. But then I didn't know exactly what to do with them. (now I know ... but I admit I wouldn't have found out that algorithm on my own)

These sorted sets A1 and A2 probably improve the speed of the Horowitz and Sahni algorithm because the range of all possible subset sums of A1 will be smaller than the desired sum s=0.5*sum(x1,x2,...,xn) and the whole range of the subset sums of A2 does not need to be checked ... but only the range [s-sum(A1), s].

Small Hint: The sorted arrays of the subset sums of A1 and A2 should both hold a 0 as the first element so the special case of one of them holding the desired value s is not overlooked.