How is it a huge improvement? Your O(SN) is the same time as the dynamic
programming solution for 0-1 knapsack isn't it?
On 8 January 2013 14:44, Don <dondod...@gmail.com> wrote:
> Yes, that is true. However, trying to find the optimal partition is
> equivalent to the 0-1 knapsack problem, which is exponential time. So
> S*N is a huge improvement over that. Does someone have a better
> solution?
> Don
>
> On Jan 7, 10:49 am, Nikhil Karnwal <sunnyk12...@gmail.com> wrote:
> > @ 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
> >
> > > --
>
> --
>
>
>
--
