BoxesOfBooks
SRM 389 · 2008-01-24 · by legakis
Problem Statement
You are packing a stack of books into some boxes, packing as many books as you can into each box without exceeding a given weight limit. Once you have packed as many books into a box as you can, you close and seal that box, and then begin filling the next one. You take the books off the stack in order, packing each one before picking up the next.
The weights of the books will be given as a
Constraints
- weights will contain between 0 and 50 elements, inclusive.
- maxWeight will be between 1 and 1000, inclusive.
- Each element of weights will be between 1 and maxWeight, inclusive.
{ 5, 5, 5, 5, 5, 5 }
10
Returns: 3
You have 6 books that weigh 5 kilograms each. Each box can hold 10 kilograms (2 books). Therefore, you need 3 boxes.
{ 51, 51, 51, 51, 51 }
100
Returns: 5
Each box can hold 100 kg, but since the books weigh 51 kg each, you can only put one in each box.
{ 1, 1, 1, 7, 7, 7 }
8
Returns: 4
You would like to put one 1 kg book and one 7 kg book in each of 3 boxes. But, since you must pack the books in order, you end up putting the three 1 kg books in one box and each of the three 7 kg books in its own box, for a total of 4 boxes.
{ 12, 1, 11, 2, 10, 3, 4, 5, 6, 6, 1 }
12
Returns: 6
{ }
7
Returns: 0
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BoxesOfBooks with a public method int boxes(vector<int> weights, int maxWeight) · 65 test cases · 2 s / 256 MB per case