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 > > > > > -- > > > -- --
