Data Structures, Algorithms, & Applications in C++
Chapter 13, Exercise 23
- (a)
-
The optimal packing uses two bins; both are full. Objects
0
and
2
are in one bin and the remaining objects are in the other.
- (b)
-
First fit puts objects
0
and
1
into the first bin; objects
2
and
3
into the second bin; and the remaining object into a third bin.
Best fit put objects
0
and
1
into the first bin; objects
2
and
3
into the second bin; and the remaining object into a third bin.
FFD puts the
6
and
1
into the first bin; the
5
and a
4
into the second bin; and the remaining 4
into a third bin.
BFD puts the
6
and
1
into the first bin; the
5
and a
4
into the second bin; and the remaining 4
into a third bin.
- (c)
-
The ratio for all methods is
3/2 = 1.5.