Problem Statement |
| | Recently you got a job and have been working in a warehouse. One of your tasks is to arrange a number of boxes one on top of another in a single pile, so that they take up less space on the floor. The boxes have different weights, as each of them holds different goods inside. Because some goods need to be accessed more often than others, certain boxes must lie above certain other boxes. Because you are very lazy, you decided to write a program that will calculate an arrangement that requires the least effort from your side.
Placing the bottom most box doesn't cost any effort. Placing each of the other boxes requires w * h effort, where w is the weight of the box, and h is the number of the boxes arranged so far. You can assume that all boxes are cubes with the same dimensions.
You are given a int[] weight, which represents the weights of the various boxes. You are also given a String[] above, where above[i][j] is '1' if the i-th box must lie above the j-th box, and '0' if there is no such constraint. Return a int[] containing the ordering of the boxes that requires the least total effort. Each element of the int[] is the 0-based index of a box, and the elements must be ordered from bottom to top. If there are multiple such orderings, return the one where the bottom box has the lowest index. If a tie still remains, return the one where the second box from the bottom has the lowest index, etc. |
| |
Definition |
| | | Class: | WarehouseJob | | Method: | stackBoxes | | Parameters: | int[], String[] | | Returns: | int[] | | Method signature: | int[] stackBoxes(int[] weight, String[] above) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | weight will contain between 2 and 16 elements, inclusive. |
| - | Each element of weight will be between 1 and 1000, inclusive. |
| - | weight and above will contain the same number of elements. |
| - | Each element of above will contain exactly n characters, where n is the number of elements in weight. |
| - | above will contain only the digits '0' and '1'. |
| - | There will always be at least one possible ordering. |
| |
Examples |
| 0) | |
| | {1,2,3} | {"000","000","000"} |
| Returns: {2, 1, 0 } | | We have boxes of weights 1, 2 and 3 and no contraints about their order. Therefore it's best to put the heaviest box on the ground, the second heaviest on top of it, and the lightest on the top. |
|
|
| 1) | |
| | {10,1,1000} | {"000","000","010"} |
| Returns: {1, 2, 0 } | | The last box must lie above the second box. |
|
|
| 2) | |
| | {891,67,455,663,626,563,110,374,325,227,463,71,603,738,401,688} | {"0000000000000000",
"0000000000000000",
"0000000000000000",
"0000000000100000",
"0000000000000010",
"0000001000000000",
"0000000000000000",
"0000000000000000",
"0000000000000000",
"0000000100000000",
"0000000000000000",
"0100000000000000",
"0100000010000000",
"0000000110000000",
"0000001000100000",
"0000001000100000"} |
| Returns: {0, 10, 3, 7, 8, 13, 6, 15, 5, 14, 4, 2, 1, 12, 9, 11 } | |
|