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
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
@Don,
Can u explain with an Example...?
With regards,
Balasubramanian Naagarajan,
Chettinad
College of Engg Tech.
On Sat, Jan 5, 2013 at 1:48 PM, Malathi malu@gmail.com wrote:
Check this. It might help.
@ 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 dondod...@gmail.com wrote:
Note that you don't need to store the entire P matrix.
Thank you for the code snippet.
What I don't understand is
if( (double)rand() / RAND_MAX 1 / k )
Here, Why do we use less than inequality?
Why won't Udit's solution of just using the minimum random number work?
On Tuesday, 1 January 2013 20:57:47 UTC+5:30, Dave wrote:
@Doom: Yes. It is
Give a Data structure to store Name-value pair like name-age
abc,12
xyz,34...
such than insert(name,value), value = search(name), name = nthentry(n),
delete(name); all can be perfomed in O(1).
Note:- after deletion order should be maintained.Ex.
ds,12
df,78
teu,54
etr,12
If delete(df) is called
