Question 3.101

71. Two-dimensional bin packing refers to the problem of packing rectangles of various sizes into a minimum number of rectangles, with the sides of the packed rectangles parallel to those of the containing rectangle.

  1. Suggest some possible real-world applications of this problem.
  2. Devise a heuristic algorithm for this problem.
  3. Give an argument to show that the problem is at least as hard to solve as the usual bin-packing problem.
  4. If you have rectangles with total area to be packed into a single rectangle of area , can the packing always be accomplished?

71.

(a) Answers will vary.

(b) Answers will vary.

(c) Packing rectangles of width 1 in an rectangle is a special case of the two-dimensional problem.

(d) Answers will vary.