Note that you don't need to store the entire P matrix. You really just
need the last column.
Don
On Jan 7, 10:29 am, Don <dondod...@gmail.com> wrote:
> You want to partition the array A into to subsets S1 and S2 such that
> you minimize |Sum(S1)-Sum(S2)|.
>
> The optimal sum for the subsets is S=SUM(A)/2
>
> Use DP to build a matrix P:
> P[i][j] = 1 if some subset of {A[0]..A[i]} has a sum of j, 0 otherwise
>
> Now find a value of i such that P[n][i] = 1 which minimizes S-i.
>
> The minimum sum is 2S-2i.
>
> Don
>
> On Jan 5, 12:58 pm, mukesh tiwari <mukeshtiwari.ii...@gmail.com>
> wrote:
>
>
>
>
>
>
>
> > Hello All!
> > I have a given array of numbers and I have to change the sign of numbers to
> > find out the minimum sum. The minimum sum will be 0 or greater than 0. Here
> > is couple of test cases
> > 1. [ 1 , 2 , 3 , 2 , 4 ]. Changing the sign [ -1 , -2 , -3 , 2 , 4 ] so
> > minimum sum will be 0.
> > 2. [ 3 , 5 , 7 , 11 , 13 ]. Changing the sign [ -3 , -5 , 7 , -11 , 13 ]
> > so minimum sum is 1.
>
> > So technically this problem boils down to divide the set into two subset
> > and find out the minimum difference. I though of DP but the number of
> > element in array could 10^5 so could some one please tell me how to solve
> > this problem ? I didn't assume that number will be positive because it was
> > not given in the problem.
>
> > Regards
> > Mukesh Tiwari
--
