Re: [algogeeks] first fit bin packing
Not sure what you are suggesting. If you bring to the root which has capacity to hold then it looks like you are disturbing the order of the bins. On Sat, May 14, 2011 at 1:34 PM, pacific :-) pacific4...@gmail.com wrote: i think we can use heaps for this problem..bring to the root which has capacity to hold and pick the root each time. If the root cannot accomodate then no other node will be able to accomodate. On Sat, May 14, 2011 at 1:26 AM, MK stardust...@gmail.com wrote: Consider the first fit strategy for online bin packing. So if you have N bins numbered 1, 2, 3..N and you are given value V, you scan them from left to right and insert V into the first bin that currently has enough capacity. In the naieve case, N insertions will take O(N^2) time. How can this be done in NlogN time? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 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 algogeeks@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] first fit bin packing
@MK: When we insert a value, we first delete that bin from the tree, then we change the old root value and then we reinsert that bin into the tree. On Sat, May 14, 2011 at 5:26 PM, MK stardust...@gmail.com wrote: Not sure what you are suggesting. If you bring to the root which has capacity to hold then it looks like you are disturbing the order of the bins. On Sat, May 14, 2011 at 1:34 PM, pacific :-) pacific4...@gmail.com wrote: i think we can use heaps for this problem..bring to the root which has capacity to hold and pick the root each time. If the root cannot accomodate then no other node will be able to accomodate. On Sat, May 14, 2011 at 1:26 AM, MK stardust...@gmail.com wrote: Consider the first fit strategy for online bin packing. So if you have N bins numbered 1, 2, 3..N and you are given value V, you scan them from left to right and insert V into the first bin that currently has enough capacity. In the naieve case, N insertions will take O(N^2) time. How can this be done in NlogN time? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 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 algogeeks@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 algogeeks@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] first fit bin packing
i think we can use heaps for this problem..bring to the root which has capacity to hold and pick the root each time. If the root cannot accomodate then no other node will be able to accomodate. On Sat, May 14, 2011 at 1:26 AM, MK stardust...@gmail.com wrote: Consider the first fit strategy for online bin packing. So if you have N bins numbered 1, 2, 3..N and you are given value V, you scan them from left to right and insert V into the first bin that currently has enough capacity. In the naieve case, N insertions will take O(N^2) time. How can this be done in NlogN time? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] first fit bin packing
Consider the first fit strategy for online bin packing. So if you have N bins numbered 1, 2, 3..N and you are given value V, you scan them from left to right and insert V into the first bin that currently has enough capacity. In the naieve case, N insertions will take O(N^2) time. How can this be done in NlogN time? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
