This problem is like 2 processor job scheduling problem ,We may get an optimal solution for different instances using different algorithm apart from brute force.Whereas Brute force covers all possible subsets but may take years to complete if N is large.
above algo fails in the following example. Eg. 2 2 2 3 3 above algo gives: T1: 2 2 3 =7 T2: 2 3 =5 But closest distribution is T1=2 2 2=6 T2 3 3=6 On Mon, May 31, 2010 at 6:24 AM, sharad kumar <[email protected]>wrote: > @abhishek:i meant after sorting split the array into 2 part each with > equal sum.... > > On Sun, May 30, 2010 at 11:45 PM, Abhishek Sharma > <[email protected]>wrote: > >> @sharad: if you find the subarrays of equal sum then the number of players >> might differ in the team... also can you tell me how will you do >> that..according to me time cmoplexity will be higher.. >> >> According to me: >> sort the palyers based on skill points (O(nlogn) --mergesort) then assign >> the players one by one to each team (O(n)) >> >> Ex: Consider 10 players to be assigned to two teams. >> skill points: 12, 12, 7, 8, 15, 19, 11, 14, 5, 10. >> >> Ans: >> after sorting: 5, 7, 8, 10, 11, 12, 12, 14, 15, 19. >> Team1: 5, 8, 12, 14, 19 >> Team2: 7, 11,12,15. >> >> This is not exactly even but i think is the closest approach. >> correct me if I am wrong.. >> >> Regards, >> Abhishek >> >> On Sun, May 30, 2010 at 8:21 PM, sharad kumar <[email protected]>wrote: >> >>> sort the players based on skill point and get the subarray of equal >>> sum...... >>> >>> >>> On Sun, May 30, 2010 at 6:58 PM, Veer Sharma >>> <[email protected]>wrote: >>> >>>> Hi Friends, >>>> >>>> This is my first post to this forum. A "Hi" to all of you and here is >>>> my first problem... >>>> >>>> Giiven int n, the total number of players and their skill-point. >>>> Distribute the players on 2 evenly balanced teams. >>>> >>>> Lets see who gives the best solution (least space complexity / least >>>> time complexity or both...) >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<algogeeks%[email protected]> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>> >>> >>> -- >>> yezhu malai vaasa venkataramana Govinda Govinda >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > yezhu malai vaasa venkataramana Govinda Govinda > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards Nikhil Agarwal Senior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
