Welcome to our site!

Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.

  • Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.

Algorithmic question

Status
Not open for further replies.

electroRF

Member
Hi
I have an algorithmic question.

You have boxes of sizes 5 x 9 x 8.

You have n items to ship.

You're required to use "first-hit" algorithm - i.e. every item you get (out of the n items) , you insert it to the first box that can contain it.

The obvious way would take O(n²) (linear-scan the boxes for every item you get).

However - You are required to do it in O(nlog(n)) - HOW?


I saw a solution which says:

"We will maintain a sorted list of boxes, first by box capacity, then by box number.

when we receive a new item, we look for the first record with capacity greater than or equal to

the iterm's weight.
"

My question is:

How do you sort boxes by capacity?


You can have an item 2x2x2, which doesn't fit into larger-capactiy box of 1x9x8, but does fist into smaller-capacity box of 2x2x2.


Thank you very much.
 

electroRF

Member
Hi Shafri
How would you sort it by dimmensions?

do you mean - sort first by X, then by Y, then by Z?

and do the search first by >=X, then by >=Y, then by >=Z?


additionally - What is the Complexity of the Sorting?
If for each item, it takes us O(N) to sort the list - isn't it O(N^2) to keep the list sorted?
 

NorthGuy

Well-Known Member
You're required to use "first-hit" algorithm - i.e. every item you get (out of the n items) , you insert it to the first box that can contain it.

To solve this problem you need a formal definition of what is "the first box that can contain it". "first ... that" assumes a certain order.

You have n items. How many boxes there's, an infinite amount? Then, it's O(n) because you do certain operation to insert one item, then repeat n times. Limited amount? Then things are getting really complex because your "first-hit" algorithm
can run out of boxes. Then what?
 

electroRF

Member
Hi North Guy - you are correct.


1. You should use minimum number of boxes (but you have infinite boxes)

2. The order the n items are given to you is random - yo can't pre-order them
 

large_ghostman

Well-Known Member
Most Helpful Member
Wow that is a great question! Shame it was moved from the micro section, I would love to know how a 30f, could be used to achieve this. At first I thought i saw the answer, but as you look at it more, the harder it seems!
Are all item's items of a fixed maximum size? and are any of a fixed minimum size?
 

shafri

Member
do you mean - sort first by X, then by Y, then by Z?
and do the search first by >=X, then by >=Y, then by >=Z?
no i mean during the sorting process, to decide an item to move up or down you use MIN criteria. such that..

Code:
if MIN(a(i).x, a(i).y, a(i).z) < MIN(a(i-1).x, a(i-1).y, a(i-1).z) then
      tmp = a(i-1)
      a(i-1)=a(i)
      a(i)=tmp
end if
 
int MIN(x,y,z) {
     return the smallest among x,y,z.
end sub

though i dont think this simple code may fullfill your need, you need to look closer into the criteria to decide if an item fit in the given box and then you can modify MIN function to suit your need. properly sorted boxes based on your criteria will enable you to binary search appropriate box in log(n) process. you know your problem clearly we dont. YMMV.
 
Last edited:

shafri

Member
there are situation when MIN criteria will not fullfill exactly just as your example above 2x2x2 box wont fit 1x9x8 item, so maybe you can use MAX criteria? you study that ;)
 

NorthGuy

Well-Known Member
1. You should use minimum number of boxes (but you have infinite boxes)

2. The order the n items are given to you is random - yo can't pre-order them

So, all the boxes are of the same size and you can put multiple items into the same box, right?

That is a very complex task. And the "first hit" algorithm will not give you the minimum number of boxes. "Frist hit" would rather minimize the speed and to do that you simple take a new box for every item - you cannot do it faster than this. This will run in O(n).

You can save some boxes, if you take two items at a time and if they fit in the same box you put them there and if not, you put one in the box and pull another item from the queue and so on. This will run in O(n).

To evolve this idea further, you can maintain a pool of items ready to be put into the boxes, then as soon as you find a set of items which fills a good portion of the box, you fill in the box and pull some new items into your pool to replace the used items. Any sort of such algorithm will run approximately in O(n) too.

Getting the absolute minimum of the boxes for the given set of items is a very complex task and I don't think an easy algorithm exists. Brute force will run way worse than O(n^2).
 

MrAl

Well-Known Member
Most Helpful Member
Hi,

You could also look into sorting according to the longest diagonal, which is sqrt(a^2+b^2+c^2), but i'd like to know more about the elements of this problem first.

When you say you have 'sizes' 5x9x8 does that mean that is the max size and there are boxes with integer sizes up to that size?

Also, what sizes can the objects be?
 

misterT

Well-Known Member
Most Helpful Member
Could you post the original description of the problem. I think you are complicating this more than originally intended (the solution suggestion talks about item weight and box capacity, you are talking about dimensions).
 

MrAl

Well-Known Member
Most Helpful Member
Hi misterT,

I'd like to see that data too as some of the posts in this thread dont make that much sense as you noticed too.
I'd also like to see what size the objects can be as well as a few example 'pickings' like this for example:
First pick: item=2x5x3, box=3x6x4
Second pick: item=3x2x6, box=5x3x8

and if the dimensions are always integer values or can they be fractional such as:
2.345 x 1.643 x 7.111
 

electroRF

Member
Hi Guys,

I'm sorry for the confusion.

Here's the original question.

You have fixed-size mail shipping boxes.
You can ship anything you want that fits in the box.
You have n items to ship and have a large supply of 5 x 9 x 8 boxes.
You want to minimize the number of boxes you use.
The first-fit algorithm is a greedy algorithm for this problem - it processes the items in the sequence in which they are first given and places them in the first box in which they fit, scanning through the boxes in increasing order.
First fit is not optimum but it never takes more than twice as many boxes as the minimum possible.

Implement first-fit to run in O(nlog(n)).
 
Status
Not open for further replies.

Latest threads

Top