int q[S] = {0};
q[0] = 1;
for(i = 0; i < N; ++i)
for(j = S; j >= A[i]; --j)
q[j] |= q[j-A[i]];
Then find the largest value i where q[i]=1, and the smallest sum is
2(S-i).
As has been pointed out, S can be large and this method can take a
long time for big input cases.
On Jan 9, 3:04 pm, prankur gupta <[email protected]> wrote:
> Hi,
>
> I have understood the solution, but here we are talking about knowing the
> path(elements in the subsets in this case).
> I saw we could use the back pointer technique, which I understood, but I'm
> not able to see how would I code this technique.
> Please try to explain me this thing.
>
> Thanks a lot in advance.
>
>
>
>
>
>
>
>
>
> On Wed, Jan 9, 2013 at 10:46 AM, Don <[email protected]> wrote:
> > My solution is equivalent to using DP for the 0-1 knapsack, but the DP
> > approach does not identify the partition, it only determines if it
> > exists. In the same way, my solution does not determine which numbers
> > to make negative. It only determines what the smallest possible sum
> > is. The DP approach to 0-1 knapsack is not really a solution, if the
> > problem is stated in the usual way: what set of objects should I put
> > in the knapsack to maximize the total. It only solves the problem:
> > what is the maximum total I can achieve.
>
> > On Jan 9, 7:12 am, Carl Barton <[email protected]> wrote:
> > > 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]>
> > > > > > > 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
>
> > > > > > --
>
> > > > --
>
> > --
>
> --
> PRANKUR GUPTA
>
> Masters Student (CSE)
> State University of New York
> Stony Brook University
> [email protected]
--
