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
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 i
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
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 wrote:
> Yes, that is true. However, trying to find the optimal partition is
> equivalent to the 0-1 knapsack problem, which is exponential time.
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 wrote:
> @ Don
> but ur's solution complexity
@ 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=100 and N=10^5.
Correct me if I am wrong.
Nikhil Karnwal
On Mon, Jan 7, 2013 at 9:04 PM, Don wrote:
> Note that you don't need to store the entire P matrix. You really just
>
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 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
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
