@divya : descending order sorting works. BRILLIANT !!
On 5/17/10, divya jain sweetdivya@gmail.com wrote:
my algo on the array 1 200 500 2000
sort the array therefore we have now 2000 500 200 1
1st array will have largest element
A= {2000}
and B={500}
sumA=2000
sumB=500
now
@divya : it's a greedy approach and again it's WRONG!
your answer for {110,100,90,70,60,10 } would be:
A = { 110, 70, 60 }
B = { 100, 90 , 10 }
the difference is 40
the correct ans:
A = { 110, 100 , 10 }
B = { 90 , 70 , 60 }
the difference is 0
i don't believe a greedy algorithm would work for
I was really not able to digest the greedy thing
Great example!!
On 5/17/10, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote:
@divya : it's a greedy approach and again it's WRONG!
your answer for {110,100,90,70,60,10 } would be:
A = { 110, 70, 60 }
B = { 100, 90 , 10 }
the
I dont think greedy or dp should be the way to approach the problem since it
does not show optimal sub-structure property.
On Mon, May 17, 2010 at 10:22 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
I was really not able to digest the greedy thing
Great example!!
On 5/17/10, Amir
One more way to do this can be:
1. sorting the number in decreasing order
2. start with 2 empty sets A and B and assign first 2 elements to each of
them (see the following example)
3. maintain the sums of A and B in variables.
4. take the next number from list and add it to the set
Algorithm to partition set of numbers into two s.t. diff bw their
sum is min and they hav equal num of elements
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
A simple DP should work. Should it not?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 4:15 PM, Sathaiah Dontula
yes u can assume even no of elements..
@ rohit please explain ur ans in detail.. thanks in advance :)
On 14 May 2010 16:23, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
A simple DP should work. Should it not?
--
Rohit Saraf
Second Year
@rohit ...
please elaborate
On Fri, May 14, 2010 at 4:23 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
A simple DP should work. Should it not?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT