Detailed Solution Would Be Appreciated 1 (125.38 KiB) Viewed 52 times
Detailed Solution Would Be Appreciated 2 (26.21 KiB) Viewed 52 times
Good news! The packing machine has now been fixed and can actually rotate products to fit into boxes. We now need to re-evaluate bids from box manufacturers. You are given a list P of n products P₁,...,Pn where product p; has length length(p;) and width width(p;) and a list B of m boxes b₁,...,bm, and a list B of m boxes b₁,...,bm where box b, has length length(b;) and width width(b;). We say that product p; rotationally fits into box b; if at least one of the following conditions hold: • length(pi) < length(b,) and width(pi) ≤ width(b;), or • width(p;) < length(b;) and length(p;) ≤ width(b;), or The total rotational fit is the total number of product-box pairs (p₁, b) such that p; rotationally fits in bj. The goal is to compute the total rotational fit. We call this the Rotational Fit Problem. width b₁ P₁ dength Figure 1: p₁ and pe rotationally fit in boxes b₁ and be so the total rotational fit is 4. Note that p₁ only rotationally fits in b₂, it does not non-rotationally fit in b₂. Note that there may be multiple products/boxes that share the same length and/or width. In this task, we will reduce this problem to that of the problem in A1, which we now call the Non- Rotational Fit Problem. Recall that in the Non-Rotational Fit Problem, you are also given a list of products and a list of boxes, each with lengths and widths. We say that product p; non-rotationally fits into box b; if length(p;) < length(b;) and width(p;) ≤ width(b;). The total non-rotational fit is the total number of product-box pairs (pi, bj) such that p; non-rotationally fits in bj. The goal is to compute the total non-rotational fit. The goal in this task is to design an algorithm that takes as input an instance I of the Rotational Fit Problem and output an instance J of the Non-Rotational Fit Problem such that the total rotational fit of I is exactly equal to the total non-rotational fit of J. b₂ Pu
(b) Your task is to implement en ta reduction from the Rotational Fit Problem to the Non- Rotational Fit Problem. In particular, design an algorithm that takes as input an instance I of the Rotational Fit Problem and outputs an instance J of the Non-Rotational Fit Problem such that the total rotational fit of I is exactly equal to the total non-rotational fit of J. For full marks, your algorithm should run in linear time, i.e. O(n + m) time. [25 marks]
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!