@ Don
but ur's solution complexity is O(S*N) which is large in case of large N
and large numbers.
Like in case of s=1000000 and N=10^5.
Correct me if I am wrong.
Nikhil Karnwal
On Mon, Jan 7, 2013 at 9:04 PM, Don <dondod...@gmail.com> wrote:
> 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
>
> --
>
>
>
--
