Re: [algogeeks] Divide an array into two equal subsets
@vishal may be ur solution is correct but if S very large then its not feasible to have matrix On Wed, Dec 29, 2010 at 10:37 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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.
Re: [algogeeks] Divide an array into two equal subsets
Expecting solution is which is independent of S On Wed, Dec 29, 2010 at 10:37 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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.
Re: [algogeeks] Divide an array into two equal subsets
What if we sort array and place first n/4 and last n/4 elements in one subarray and other n/2 in the 2nd subarray. On Fri, Dec 31, 2010 at 4:08 AM, Anand anandut2...@gmail.com wrote: http://anandtechblog.blogspot.com/2010/07/partition-of-array.html On Thu, Dec 30, 2010 at 12:35 AM, vishal raja vishal.ge...@gmail.comwrote: This means , You can make a sum = j , with or without using the item i , while calculating P[i][j]. So you can have another counter Count2 which will have the count for such items. So you will calculate P as discussed before but You will add 1 in Count2[i][j] whenever you find that case. add one in count[i][j] in any of P = 1 case. in the end you'll search for the max value of j (closest to S/2) for all P values which has this property on value of i . 1. i = 50 2. for all i 50 i-count2[i][j] = 50 I think this will do. Check it out. On Thu, Dec 30, 2010 at 12:41 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: vishal , what will we do to count when both p[i-1][j] and p[i-1][j-a[i]] is true . On Thu, Dec 30, 2010 at 12:36 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: Thanks everybody for wonderful support and special thanks to Vishal raja. . But i was bit apprehensive about your last solution . . i will test it :) and let you know as well . Thanks . . . . On Thu, Dec 30, 2010 at 11:52 AM, vishal raja vishal.ge...@gmail.com wrote: But the same solution I've given above can give you the solution for this problem . In the formed table of P[i][j] , you can take another variable attached to it as count[i][j] for how many items we have selected yet. So you gotta find , the max. value of j which has count = 50. count[i][j] = count[i-1][j] if P(i-1,j) ==1 count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 else count[i][j] = 0 On Thu, Dec 30, 2010 at 11:42 AM, vishal raja vishal.ge...@gmail.com wrote: yeah, My bad. Missed that. On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares wladimir...@gmail.com wrote: Sum up all the number and divide by 2 Using the algorithm subset problem to find a number close to median Wladimir Araujo Tavares Federal University of Ceará On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Rahul Patil -- You received this message
Re: [algogeeks] Divide an array into two equal subsets
But the same solution I've given above can give you the solution for this problem . In the formed table of P[i][j] , you can take another variable attached to it as count[i][j] for how many items we have selected yet. So you gotta find , the max. value of j which has count = 50. count[i][j] = count[i-1][j] if P(i-1,j) ==1 count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 else count[i][j] = 0 On Thu, Dec 30, 2010 at 11:42 AM, vishal raja vishal.ge...@gmail.comwrote: yeah, My bad. Missed that. On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares wladimir...@gmail.com wrote: Sum up all the number and divide by 2 Using the algorithm subset problem to find a number close to median Wladimir Araujo Tavares *Federal University of Ceará * On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 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.
Re: [algogeeks] Divide an array into two equal subsets
Thanks everybody for wonderful support and special thanks to Vishal raja. . But i was bit apprehensive about your last solution . . i will test it :) and let you know as well . Thanks . . . . On Thu, Dec 30, 2010 at 11:52 AM, vishal raja vishal.ge...@gmail.com wrote: But the same solution I've given above can give you the solution for this problem . In the formed table of P[i][j] , you can take another variable attached to it as count[i][j] for how many items we have selected yet. So you gotta find , the max. value of j which has count = 50. count[i][j] = count[i-1][j] if P(i-1,j) ==1 count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 else count[i][j] = 0 On Thu, Dec 30, 2010 at 11:42 AM, vishal raja vishal.ge...@gmail.com wrote: yeah, My bad. Missed that. On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares wladimir...@gmail.com wrote: Sum up all the number and divide by 2 Using the algorithm subset problem to find a number close to median Wladimir Araujo Tavares Federal University of Ceará On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- 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. -- 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. -- 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. -- 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.
