This should be solvable by dp as in knapsack problem where value = weights and W = S/2. where S = sum of all elements in the array.
The claim here is diff in sum of two subsets will be minimum when one maximizes a sub-set sum (say s) where sum (s) is closest to S/2. Divya's problem is looking for balanced sets which may or may not be feasible using a modified form of this. On Thu, Jun 3, 2010 at 7:06 PM, saurabh gupta <sgup...@gmail.com> wrote: > yep, constraints are fewer here > but in terms of problem statement 'same' and 'similar' can create > diversions. > > > On Thu, Jun 3, 2010 at 6:01 PM, Rohit Saraf > <rohit.kumar.sa...@gmail.com>wrote: > >> Still the solution will be similar and actually a bit simpler..... >> >> -- >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> -- >> 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 from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. > Says he feels all alone in a threatening world where what lies ahead is > vague and uncertain. Doctor says "Treatment is simple. Great clown > Pagliacci is in town tonight. Go and see him. That should pick you up." Man > bursts into tears. Says "But, doctor...I am Pagliacci." > -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says "Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up." Man bursts into tears. Says "But, doctor...I am Pagliacci." -- 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 from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
