Re: [algogeeks] Re: first fit bin packing
@chinna: the question asks for first fit, not best fit
On Sun, May 22, 2011 at 1:03 AM, pacific :-) wrote:
> @ankit: I didn't undertand ur explanation for why a sort wont work.
>
> 1. Sort the bins by the left over space.
> 2. For a new value to be inserted , do a binary search and locate the best
> fit.
> 3. For the bucket we are adding this new element , its left over space
> reduces ...so now do a binary search to find its new location and move it to
> the new location.
>
> O(nlogn) {for initial sort} + n * { logn (for search ) + logn (for moving
> the box to which we are adding ) }
> Total complexity = O(nlogn)
>
> Correct me if i'm wrong.
>
> On Tue, May 17, 2011 at 7:05 PM, ankit sambyal wrote:
>
>> @monsieur: we can't solve the problem by the way u suggest because we
>> have to sort it by bin number but we have to find the first fit according to
>> the left over space in the bin. So, in the worst case it will take more than
>> O(n*log(n))time If u need any clarifications feel free to comment
>>
>>
>> regards,
>> Ankit
>>
>>
>>
>>
>>
>>
>> On Tue, May 17, 2011 at 5:52 AM, MONSIEUR wrote:
>>
>>> guys why cant we simply sort bins using merge sort or any comparison
>>> sort and then use binary search to find out the first available
>>> bin.t(n)=O(nlgn)+n*(lgn)=O(nlgn).
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> 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] Re: first fit bin packing
@ankit: I didn't undertand ur explanation for why a sort wont work.
1. Sort the bins by the left over space.
2. For a new value to be inserted , do a binary search and locate the best
fit.
3. For the bucket we are adding this new element , its left over space
reduces ...so now do a binary search to find its new location and move it to
the new location.
O(nlogn) {for initial sort} + n * { logn (for search ) + logn (for moving
the box to which we are adding ) }
Total complexity = O(nlogn)
Correct me if i'm wrong.
On Tue, May 17, 2011 at 7:05 PM, ankit sambyal wrote:
> @monsieur: we can't solve the problem by the way u suggest because we have
> to sort it by bin number but we have to find the first fit according to the
> left over space in the bin. So, in the worst case it will take more than
> O(n*log(n))time If u need any clarifications feel free to comment
>
>
> regards,
> Ankit
>
>
>
>
>
>
> On Tue, May 17, 2011 at 5:52 AM, MONSIEUR wrote:
>
>> guys why cant we simply sort bins using merge sort or any comparison
>> sort and then use binary search to find out the first available
>> bin.t(n)=O(nlgn)+n*(lgn)=O(nlgn).
>>
>> --
>> 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.
>
--
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.
Re: [algogeeks] Re: first fit bin packing
@ila: When a value has been added to the bin, its value will definitely change. First we have to delete the previous bin from the AVL tree and then we have to insert that bin into the AVL tree with the updated value. If u need any more clarifications, plz feel free to comment. Regards, Ankit On Tue, May 17, 2011 at 6:35 AM, ankit sambyal wrote: > @monsieur: we can't solve the problem by the way u suggest because we have > to sort it by bin number but we have to find the first fit according to the > left over space in the bin. So, in the worst case it will take more than > O(n*log(n))time If u need any clarifications feel free to comment > > > regards, > Ankit > > > > > > > On Tue, May 17, 2011 at 5:52 AM, MONSIEUR wrote: > >> guys why cant we simply sort bins using merge sort or any comparison >> sort and then use binary search to find out the first available >> bin.t(n)=O(nlgn)+n*(lgn)=O(nlgn). >> >> -- >> 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] Re: first fit bin packing
@monsieur: we can't solve the problem by the way u suggest because we have to sort it by bin number but we have to find the first fit according to the left over space in the bin. So, in the worst case it will take more than O(n*log(n))time If u need any clarifications feel free to comment regards, Ankit On Tue, May 17, 2011 at 5:52 AM, MONSIEUR wrote: > guys why cant we simply sort bins using merge sort or any comparison > sort and then use binary search to find out the first available > bin.t(n)=O(nlgn)+n*(lgn)=O(nlgn). > > -- > 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.
[algogeeks] Re: first fit bin packing
guys why cant we simply sort bins using merge sort or any comparison sort and then use binary search to find out the first available bin.t(n)=O(nlgn)+n*(lgn)=O(nlgn). -- 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] Re: first fit bin packing
@Ankit
Wht about updating the nodes when a value has been added to the
bin ??
The left over space has to be modified n so is the tree.
On May 17, 1:17 pm, ankit sambyal wrote:
> Hey Guys, here is my solution :
>
> we can use AVL trees for this. We will use the left over space in the bins
> as the node value. Since we hv N bins and inserting 1 element in the AVL
> tree takes log(N) time , so inserting N elements will take n*log(N) time.
> So, AVL tree construction will take N*log(N) time(it will be lesser than
> this, a little thought will reveal u that. But even if we take n*log(N), we
> can solve the problem in N*log(N) time). Now we have to search the first
> node having node value i.e left over space greater than the given value V.
>
> here is the structure for the node:
>
> typedef int Element;
> struct node;
> typedef struct node avlNode;
> typedef avlNode *AvlTree;
> struct node{
> Element root;
> int bucket_number;
> AvlTree left;
> AvlTree right;
> int weight; // required for update operation after insertion and deletion
>
> };
>
> here is the algo for searching:
>
> int find() //appropriate arguements are passed
> {
> if root < V
> go to right sub tree
> else
> {
> if (node->bucket_number < k) // k is a global variable which holds
> the bucket number of the bin having the smallest bucket number which can
> //hold the value V
> {
> k=node->bucket_number
> }
>
> first go to left sub tree
> then go to right sub tree
>
> }
>
> }
>
> It is clear that the time complexity of the whole process is O(n*log(n))
> If anybdy has any doubt, feel free to comment
>
> Thanks and Regards,
> Ankit
>
> On Mon, May 16, 2011 at 9:37 PM, anshu mishra
> wrote:
>
>
>
>
>
>
>
> > void query(int w, int s, int e, int node)
> > {
> > if (s==e)
> > {
> > tree[node] -= w;
> > prpogateNewMax(node);
>
> > return;
> > }
> > mid = (s+e)>>1;
> > if (tree[(node<<1)+1] > = w) query(w, s, mid, (node<<1)+1);
> > else query(w, mid+1, e, (node<<1)+2);
> > }
>
> > void prpogateNewMax(int node)
> > {
> > if (node == 0) return;
> > int par = (node-1)>>1;
> > int a = tree[(par<<1)+1];
> > int b = tree[(par<<1)+2];
>
> > tree[par] = a > b ? a : b;
>
> > prpogateNewMax(par);
> > }
>
> > Now I think everything is clear. For a single query we have traverse from
> > root to leaf than leaf to root. total 2*log(n); So finally for n queries
> > order will be O(n*logn);
>
> > --
> > 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] Re: first fit bin packing
Hey Guys, here is my solution :
we can use AVL trees for this. We will use the left over space in the bins
as the node value. Since we hv N bins and inserting 1 element in the AVL
tree takes log(N) time , so inserting N elements will take n*log(N) time.
So, AVL tree construction will take N*log(N) time(it will be lesser than
this, a little thought will reveal u that. But even if we take n*log(N), we
can solve the problem in N*log(N) time). Now we have to search the first
node having node value i.e left over space greater than the given value V.
here is the structure for the node:
typedef int Element;
struct node;
typedef struct node avlNode;
typedef avlNode *AvlTree;
struct node{
Element root;
int bucket_number;
AvlTree left;
AvlTree right;
int weight;// required for update operation after insertion and deletion
};
here is the algo for searching:
int find() //appropriate arguements are passed
{
if root < V
go to right sub tree
else
{
if (node->bucket_number < k)// k is a global variable which holds
the bucket number of the bin having the smallest bucket number which can
//hold the value V
{
k=node->bucket_number
}
first go to left sub tree
then go to right sub tree
}
}
It is clear that the time complexity of the whole process is O(n*log(n))
If anybdy has any doubt, feel free to comment
Thanks and Regards,
Ankit
On Mon, May 16, 2011 at 9:37 PM, anshu mishra wrote:
> void query(int w, int s, int e, int node)
> {
> if (s==e)
> {
> tree[node] -= w;
> prpogateNewMax(node);
>
> return;
> }
> mid = (s+e)>>1;
> if (tree[(node<<1)+1] > = w) query(w, s, mid, (node<<1)+1);
> else query(w, mid+1, e, (node<<1)+2);
> }
>
> void prpogateNewMax(int node)
> {
> if (node == 0) return;
> int par = (node-1)>>1;
> int a = tree[(par<<1)+1];
> int b = tree[(par<<1)+2];
>
> tree[par] = a > b ? a : b;
>
> prpogateNewMax(par);
> }
>
> Now I think everything is clear. For a single query we have traverse from
> root to leaf than leaf to root. total 2*log(n); So finally for n queries
> order will be O(n*logn);
>
> --
> 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] Re: first fit bin packing
void query(int w, int s, int e, int node)
{
if (s==e)
{
tree[node] -= w;
prpogateNewMax(node);
return;
}
mid = (s+e)>>1;
if (tree[(node<<1)+1] > = w) query(w, s, mid, (node<<1)+1);
else query(w, mid+1, e, (node<<1)+2);
}
void prpogateNewMax(int node)
{
if (node == 0) return;
int par = (node-1)>>1;
int a = tree[(par<<1)+1];
int b = tree[(par<<1)+2];
tree[par] = a > b ? a : b;
prpogateNewMax(par);
}
Now I think everything is clear. For a single query we have traverse from
root to leaf than leaf to root. total 2*log(n); So finally for n queries
order will be O(n*logn);
--
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] Re: first fit bin packing
sorry, above mail is addressed to Anshu. :P
On Mon, May 16, 2011 at 10:08 PM, Akshata Sharma
wrote:
> @Anuj:
> I have a doubt. I am not getting how to update all the nodes up the leaf
> node which we found in the query for our value. The biggest capacity bin for
> all the above nodes will change once we modify the leaf value. How to
> propagate this upwards? After each query, do we again need to run the update
> operation on all array values after modifying the array index where we found
> the bin for our query?
>
> On Mon, May 16, 2011 at 6:32 PM, anshu wrote:
>
>> we can use BIT or segment trees.
>>
>> algorithm using segment tree
>>
>> 1. intialize all node wid zeros
>> 2. read the array element according their index update the node value.
>>
>> void update(int s, int e, int k, int node)
>> {
>> if (tree[node] < ar[k]) tree[node] = ar[k];
>> if (s==e) return;
>> mid = (s+e)>> 1;
>> if (k <= mid) update(s, mid, k, (node<<1)+1);
>> else update(mid+1, e, k, (node<<1)+2);
>> }
>>
>> 3. now ur query part start
>> if left nodes value greater or equals to given value V then
>> goto left node otherwise goto right node as soon as you reach the leaf
>> node that will be your first fit bin and subtract value v from leaf
>> node. and accordingly update value from leaf to root.
>>
>> if the algorithm is not clear. you are welcome to ask.
>>
>> --
>> 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] Re: first fit bin packing
@Anuj:
I have a doubt. I am not getting how to update all the nodes up the leaf
node which we found in the query for our value. The biggest capacity bin for
all the above nodes will change once we modify the leaf value. How to
propagate this upwards? After each query, do we again need to run the update
operation on all array values after modifying the array index where we found
the bin for our query?
On Mon, May 16, 2011 at 6:32 PM, anshu wrote:
> we can use BIT or segment trees.
>
> algorithm using segment tree
>
> 1. intialize all node wid zeros
> 2. read the array element according their index update the node value.
>
> void update(int s, int e, int k, int node)
> {
> if (tree[node] < ar[k]) tree[node] = ar[k];
> if (s==e) return;
> mid = (s+e)>> 1;
> if (k <= mid) update(s, mid, k, (node<<1)+1);
> else update(mid+1, e, k, (node<<1)+2);
> }
>
> 3. now ur query part start
> if left nodes value greater or equals to given value V then
> goto left node otherwise goto right node as soon as you reach the leaf
> node that will be your first fit bin and subtract value v from leaf
> node. and accordingly update value from leaf to root.
>
> if the algorithm is not clear. you are welcome to ask.
>
> --
> 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.
[algogeeks] Re: first fit bin packing
we can use BIT or segment trees.
algorithm using segment tree
1. intialize all node wid zeros
2. read the array element according their index update the node value.
void update(int s, int e, int k, int node)
{
if (tree[node] < ar[k]) tree[node] = ar[k];
if (s==e) return;
mid = (s+e)>> 1;
if (k <= mid) update(s, mid, k, (node<<1)+1);
else update(mid+1, e, k, (node<<1)+2);
}
3. now ur query part start
if left nodes value greater or equals to given value V then
goto left node otherwise goto right node as soon as you reach the leaf
node that will be your first fit bin and subtract value v from leaf
node. and accordingly update value from leaf to root.
if the algorithm is not clear. you are welcome to ask.
--
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.
