We are given a set of boxes B, where each box i is represented by its...

 

Transcribed Image Text:

We are given a set of boxes B, where each box i is represented by its dimensions (ai, bi, ci), denoting its length, width, and height, respectively. Given are a set of items T, where each item j is represented by its dimensions (a,, bj, C;), denoting its length, width, and height, respectively. Note that for any two items i and j with i < j, we know a aj, bi b, and ci cj. We can put at most 1 item in a box. Item j can be put into box i if one of the following is true: aj a, and b; b, and c; ci; or aj a, and b; c and cj bij or a b, and b; a, and c; c; or a, b; and b; c and c; ai; or aj c and b; b, and c; a,; or a; c and b; a, and c; b. (a) (10 points) Please design an efficient greedy algorithm for solving this problem, briefly argue the running time and prove the correctness of the algorithm. (b) (5 points) Given the boxes and items provided below, please implement your algorithm and provide the optimal packing solution of your algorithm, e.g., put item 1 to box 1, ... 7 boxes of size {(2, 1,5), (2, 7, 5), (4, 6, 8), (5, 8, 3), (9, 6, 8), (8, 2, 5), (5,2,4)}. 7 items of size {(2, 2, 1), (2, 3, 2), (5, 3, 2), (5, 8, 4), (5, 8, 5), (5, 9, 8), (6, 9, 8)}. We are given a set of boxes B, where each box i is represented by its dimensions (ai, bi, ci), denoting its length, width, and height, respectively. Given are a set of items T, where each item j is represented by its dimensions (a,, bj, C;), denoting its length, width, and height, respectively. Note that for any two items i and j with i < j, we know a aj, bi b, and ci cj. We can put at most 1 item in a box. Item j can be put into box i if one of the following is true: aj a, and b; b, and c; ci; or aj a, and b; c and cj bij or a b, and b; a, and c; c; or a, b; and b; c and c; ai; or aj c and b; b, and c; a,; or a; c and b; a, and c; b. (a) (10 points) Please design an efficient greedy algorithm for solving this problem, briefly argue the running time and prove the correctness of the algorithm. (b) (5 points) Given the boxes and items provided below, please implement your algorithm and provide the optimal packing solution of your algorithm, e.g., put item 1 to box 1, ... 7 boxes of size {(2, 1,5), (2, 7, 5), (4, 6, 8), (5, 8, 3), (9, 6, 8), (8, 2, 5), (5,2,4)}. 7 items of size {(2, 2, 1), (2, 3, 2), (5, 3, 2), (5, 8, 4), (5, 8, 5), (5, 9, 8), (6, 9, 8)}.