@gaurav both things are same, matrix is a simple and efficient way to
do problem like this.
.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group,
yes we would use 2 dimensional array to store the values inbetween but the
main question here is that is the reccurence realation correct??
On Mon, May 9, 2011 at 11:31 AM, anshu anshumishra6...@gmail.com wrote:
@gaurav both things are same, matrix is a simple and efficient way to
do problem
@gaurav
f(i, j) = {(total number we need to make sum j including ith number in
array), if its not possible than -1};
f(i, j) = f(i-1, j-ar[i]) + 1 -- if (i-1, j-ar[i]) != -1;
answer will be the largest j for which f(i, j) will be exactly equals to
n/2;
there is something more in this but when
1.Add 0 to the array if the number of elements in the given array is
odd.
2.Count the frequency of each element or we can simply sort it.
3.If the frequency is even for any element then that element can be
distributed among two parts equally(say p1 and p2).
4.For the elements having odd
Use KnapSack DP. suppose the sum of element = s and number of elements
= n make a 2-dimesnsional array of size n * ((s+1)/2); I think that
much hint is enough.
if we think little bit more we can optimize it also.
--
You received this message because you are subscribed to the Google Groups
@anshu
then shall we use the foll reccurence realation??
1i=n
S=(s+1)/2
f(i,S)= min( f(i-1, S), f(i-1, S- ar[i]) )
On Mon, May 9, 2011 at 10:42 AM, anshu anshumishra6...@gmail.com wrote:
Use KnapSack DP. suppose the sum of element = s and number of elements
= n make a 2-dimesnsional array
simple..
sum all the n elements..
a= floor(sum/2)
b=sum-a
output is a b
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
@cegprakash: it doesnt ensure that both the arrays will be having same
number of elements
On Sat, May 7, 2011 at 10:10 PM, cegprakash cegprak...@gmail.com wrote:
simple..
sum all the n elements..
a= floor(sum/2)
b=sum-a
output is a b
--
You received this message because you are
sorry, i misunderstood the problem statement
On Sun, May 8, 2011 at 10:53 AM, Aakash Johari aakashj@gmail.comwrote:
@cegprakash: it doesnt ensure that both the arrays will be having same
number of elements
On Sat, May 7, 2011 at 10:10 PM, cegprakash cegprak...@gmail.com wrote:
