Problem Statement
Your company has a new box loading robot. It is your job to program it to pack items into the shipping boxes. The robot does not have a very large program memory so you are restricted to placing all the items into the boxes in the same orientation. Each item is a rectangular solid with dimensions itemX by itemY by itemZ. The box is also rectangular with the dimensions boxX by boxY by boxZ. The items can be placed in the box in any orthogonal orientation (ie. the sides of the items must be parallel to the sides of the box), but only whole items can be placed in the box. Your task here is to determine the greatest number of items that can be packed into the box (with all the items in the same orientation).
For example, if the box is 100x98x81 units and the items are 3x5x7 units, then orienting the items so they are 5x7x3, allows them to fit in the box in a 20x14x27 grid, filling the entire box, which is optimal: 7560 items.
Definition
- Class:
- BoxLoader
- Method:
- mostItems
- Parameters:
- int, int, int, int, int, int
- Returns:
- int
- Method signature:
- int mostItems(int boxX, int boxY, int boxZ, int itemX, int itemY, int itemZ)
- (be sure your method is public)
Notes
- There are six possible orientations for an item.
Constraints
- boxX, boxY and boxZ will be between 1 and 1000 inclusive.
- itemX, itemY and itemZ will be between 1 and 1000 inclusive.
Examples
100
98
81
3
5
7
Returns: 7560
The example from above.
10
10
10
9
9
11
Returns: 0
That's not going to fit!
201
101
301
100
30
20
Returns: 100
There is going to be some empty space in this box, as none of the box dimensions is an exact multiple of an item dimension. Orienting the items so that the 30 unit dimension goes in the box's 301 unit direction wastes the least space. 10 items can fit leaving only one unit of waste in that dimension.
913
687
783
109
93
53
Returns: 833
A less obvious example of minimizing the wasted space.
6
5
4
3
2
1
Returns: 20
115
113
114
3
5
7
Returns: 13984
115
113
114
3
7
5
Returns: 13984
115
113
114
5
3
7
Returns: 13984
115
113
114
5
7
3
Returns: 13984
115
113
114
7
3
5
Returns: 13984
115
113
114
7
5
3
Returns: 13984
4
3
2
2
2
2
Returns: 2
1000
1000
1000
1000
1000
1000
Returns: 1
1
1
1
1
1
1
Returns: 1
2
3
4
1
1
1
Returns: 24
42
47
49
2
3
4
Returns: 3864
19
15
17
9
8
10
Returns: 4
901
900
902
451
452
453
Returns: 2
101
77
43
11
10
7
Returns: 420
999
888
777
888
888
888
Returns: 0
999
989
987
11
13
19
Returns: 351728
100
1000
10
25
7
19
Returns: 208
51
37
29
27
33
39
Returns: 1
1
1
1
1000
999
2
Returns: 0
788
887
878
777
778
877
Returns: 1
18
121
10
11
9
2
Returns: 110
913
687
783
109
93
53
Returns: 833
105
121
169
5
13
11
Returns: 3003
100
200
300
200
100
300
Returns: 1
1
100
1
2
2
2
Returns: 0
1
2
3
3
2
1
Returns: 1
4
100
100
5
1
1
Returns: 8000