[Link]
uk
Wiltshire
Many real life problems require complete (or exhaustive)
Decision Maths
enumeration, i.e. looking at all possibilities, to find the
best/optimal solution
for large problems, this exhaustive algorithm is almost
impossible to implement.
For practicality, we use heuristic algorithms
strategies or just rules of thumb
will usually find good solution, but not guaranteed the
best/optimal
For Bin-packing problem
Heuristic algorithm First-fit, First-fit decreasing
Exhaustive algorithm Full bins
Bin-packing Algorithms
The Bin-packing problem
Heuristic Algorithms
Wiltshire
The Bin-packing problem deals with packing boxes of
the same width and depth but different heights into
bins.
The Bin-packing problem
Wiltshire
Its best to look at an example to understand
how the Bin-packing problem works.
Here are 10 boxes, A to J with heights
(in dm) as follows.
B
A
Box
Height
Clearly you can see that the depth and width of the
How would you pack the boxes into bins that
The Bin-packing problem
The Bin-packing problem
are 15dm high.
bins remains the same so we can represent the
problem in 2-dimensions.
Wiltshire
First-fit algorithm
Wiltshire
First-fit decreasing algorithm.
Box
Box
D
A
F
B
H
C
B
D
FI
C
G
J
H
AI
G
J
Height
Height
3
9
9
7
8
4
7
9
6
9
4
3
4
8
3
6
3
4
15
C(4)
G(3) H(8)
I(6)
B(7)
D(9)
A(3)
E(7)
F(9)
J(4)
Bin 1 Bin 2 Bin 3 Bin 4 Bin 5
The idea is that you place the first box in the
first available space, working from the left every
time.
Here box A goes in to bin 1.
Now box B and C will also fit in to bin 1.
Box D does not fit in bin 1 so it goes in the next
space which is bin 2.
Box E will not go in bin 1 or 2 so it is placed in
bin 3.
Similar with F, it skips over Bins 1, 2 and 3 to go
in bin 4.
G cannot go in bin 1 but it does slot into bin 2.
H will skip 1 and 2 and fill up bin 3.
I skips 1, 2 and 3 to fill up 4.
J must be placed in a new bin.
15
I(6)
C(4) B(7)
A(3)
J(4)
D(9) F(9) H(8)
E(7)
G(3)
Bin 1 Bin 2 Bin 3 Bin 4 Bin 5
This is exactly the same method as
the first-fit algorithm with one
exception.
The difference this time is that the
boxes are placed in descending order
of size before the algorithm is applied.
You should use one of the sorting
algorithms from last lesson to do this.
Now we can apply the algorithm
This algorithm is not guaranteed to
give you the best (or optimal)
solution.
However it is more likely to do so than
just the First-fit algorithm.
The Bin-packing problem
Wiltshire
Full bin combinations.
Height
This is not an algorithmic process but
15
I(6)
A(3)
Wiltshire
This bin-packing problem can now be
Box
G(3)
The Ferry Loading problem
more common sense.
J(4)
You literally make sure that each bin is
B(7)
used to its full potential.
C(4)
If you start by placing box D in bin 1 (No
particular reason).
D(9) F(9) H(8)
E(7)
Now box I can also go in bin 1 and it will
fill all the space because 9 + 6 = 15.
What other combinations will create full
bins?
Bin 1 Bin 2 Bin 3 Bin 4 Bin 5
This is actually the optimal solution for
applied to lots of practical real life
situations.
You can change what the boxes and
bins represent.
We are going to look at how to load
vehicles on to a ferry.
Here the lanes on the ferry will be the
bins and the vehicles will be the boxes.
this particular problem.
The Ferry Loading problem
Wiltshire
A small car-ferry has three lanes, each 20m long.
The following vehicles are waiting to be loaded.
Oil tanker
Truck
Coach
Car
13m
7m
12m
4m
Insertion sort algorithm
Van
Truck
Car
Lorry
3m
6m
4m
11m
on to the trip.
Can all the vehicles be taken on the trip?
Box
A
13
B
3
C
7
D
6
E
12
F
4
G
4
H
11
Box
Height
13
3
7
6
12
4
4
11
Box
Height
The Ferry Loading problem
Wiltshire
Solution
A
13
13
B
3
13
3
A
13
C
7
13
7
3
E
12
D
6
13
7
6
3
H
11
13
12
7
6
3
C
7
E
12
F
4
13
12
7
6
4
3
13
12
7
6
4
4
3
D
6
F
4
G
4
H
11
G
4
B
3
13
12
11
7
6
4
4
3
The Disc storage problem
Wiltshire
A software company has a new program that they
Box
Height
13
12
11
First-fit decreasing
Full Bin combinations
B(3) G(4)
G(4)
C(7)
Wiltshire
First we need to sort the numbers.
Use the first-fit decreasing algorithm to load all these vehicles
Height
The Ferry Loading problem
C(7)
D(6)
D(6) F(4)
F(4)
want to sell on CD`s.
Broken down the program looks like this.
Program
Size (mb)
C D
G H
600 200 450 250 300 250 150 200 100 150
50
100
Each of the CD`s they will use can hold 700mb.
How many CD`s will the company need if they plan on
A(13) E(12)
A(13)
H(11)
H(11) E(12)
producing 50 000 copies of the program.
Program
B(3)
Lane 1 Lane 2 lane 3
Size (mb)
H G
600 450 300 250 250 200 200 150 150 100 100
K
50
Lane 1 Lane 2 lane 3
The Disc storage problem
The Plumbing Problem
Wiltshire
A plumber is using lengths of pipes 12 feet long and
Solution
wishes to cut these lengths.
A
Program
Size (mb)
H G
600 450 300 250 250 200 200 150 150 100 100
G
D
I
(250)
J
F
(250) H
A
(600) C
(200)
(450) E
B
(300)
(200)
The Plumbing Problem
Number
50
combinations or by the first-fit
decreasing algorithm.
Here the solution is done using the
first fit decreasing algorithm.
The program will fit exactly on to 4
CD`s.
The company will need
4 x 50 000 = 200 000 CD`s.
Disc 1 Disc 2 Disc 3 Disc 4
Length
(ft)
This can be solved using full bin
Length
(ft)
Number
What is the best way of achieving this so that he
wastes as little pipe as possible.
Wiltshire
First change the table to assign each length of
pipe a name.
Now you can apply the first-fit decreasing
algorithm.
You can now easily see the full bin combinations.
Pipe
Length
K(2) J(3)
D(4) E(4)
Wiltshire
F(4) I(3)
A(7) B(7) C(6)
H(3)
A B C D E F G H
7 7
6 4 4
4 3
3 3
J K L
3
2 2
K(2) L(2) J(3)
F(4)
I(3) H(3)
G(3)
E(4)
A(7) B(7) C(6)
G(3) L(2)
D(4)
Pole 1 Pole 2 pole 3 Pole 4 Pole 5
Pole 1 Pole 2 pole 3 Pole 4
