Statistics

Problem Statement for "BoxesOfBooks"

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 int[] weights, where the first element is the weight of the book on top of the stack and the last element is the weight of the book on the bottom of the stack. The maximum weight that can fit into each box will be given as an int maxWeight. Return the minimum number of boxes you will need.

Definition

Class:
BoxesOfBooks
Method:
boxes
Parameters:
int[], int
Returns:
int
Method signature:
int boxes(int[] weights, int maxWeight)
(be sure your method is public)

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.

Examples

  1. { 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.

  2. { 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.

  3. { 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.

  4. { 12, 1, 11, 2, 10, 3, 4, 5, 6, 6, 1 }

    12

    Returns: 6

  5. { }

    7

    Returns: 0

  6. { 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

    1000

    Returns: 1

  7. { 96, 758, 465, 581, 802, 790, 599, 272, 544, 641, 600, 420, 129, 600, 810, 264, 340, 849, 405, 415, 420, 115, 836, 124, 681, 535, 620, 309, 182, 201, 841, 214, 608, 848 }

    849

    Returns: 25

  8. { 19, 22, 2, 90, 81, 19, 87, 59, 72, 51, 86, 25, 51, 12, 39, 15, 66, 23, 78, 43, 19, 71, 15, 35, 76, 41, 55, 28, 50, 10, 78, 3, 27, 46, 77, 54, 75, 37, 57, 48, 59, 29 }

    92

    Returns: 29

  9. { 5, 250, 304, 157, 292, 53, 352, 209, 97, 22, 122, 46, 165, 55, 94, 151, 60, 58, 185, 28, 215, 250, 359, 174, 70, 121, 173, 190, 317, 286, 222, 65, 275, 216, 105, 48, 162, 96, 356, 184, 285 }

    365

    Returns: 23

  10. { 465, 618, 513, 264, 181, 523, 603, 114, 291, 25, 660, 256, 325, 382, 646, 127, 694, 478, 2, 696, 523, 232, 183, 641, 284, 147, 376, 192, 570, 648, 116, 97, 9, 59, 76, 354, 478, 489 }

    707

    Returns: 26

  11. { 15, 4, 30, 16, 35, 17, 36, 37, 27, 1, 26, 29, 23, 45, 28, 46, 39, 10, 24, 43, 43, 47, 26, 17, 30, 5, 29, 2, 36, 3, 35, 5, 13, 28 }

    48

    Returns: 24

  12. { 370, 99, 200, 102, 68, 362, 246, 133, 274, 385, 52, 324, 186, 125, 88, 278, 241, 277, 387, 312, 17, 239, 316, 300, 320, 374, 251, 301, 266, 72, 109 }

    389

    Returns: 23

  13. { 684, 709, 313, 719, 100, 328, 127, 672, 477, 527, 788, 405, 132, 712, 86, 341, 600, 338, 835, 11, 490, 680, 152, 291, 87, 108, 44, 371, 788, 588, 299, 565, 738, 326, 712, 339, 101, 379, 815, 712 }

    844

    Returns: 29

  14. { 201, 128, 69, 133, 19, 254, 201, 75, 128, 78, 220, 38, 250, 109, 292, 28, 240, 27, 295, 67, 35, 299, 165, 275, 115, 89, 138, 33, 55, 63, 129, 85, 66, 212, 281, 168, 29, 106, 219, 100, 258, 266, 149, 79, 59, 13, 206, 90, 110, 252 }

    299

    Returns: 31

  15. { 999, 1, 1 }

    999

    Returns: 2

  16. { 171, 123, 535, 146, 597, 153, 151, 408, 9, 110, 90, 46, 579, 617, 401, 108, 51, 106, 644, 571, 482, 380, 437, 429, 149, 533, 457, 73, 623, 496, 438, 82, 170, 447, 146, 29 }

    665

    Returns: 23

  17. { 254, 265, 431, 436, 218, 347, 217, 574, 209, 420, 559, 416, 458, 338, 466, 387, 426, 335, 79, 337, 570, 508, 123, 187, 232, 487, 304, 348, 199, 176, 519, 188, 272, 165, 512, 132, 257, 303 }

    597

    Returns: 30

  18. { 367, 86, 186, 105, 302, 250, 303, 3, 141, 124, 133, 228, 179, 188, 123, 41, 245, 302, 245, 269, 253, 269, 335, 126, 346, 338, 383, 1, 205, 370, 198, 349, 24, 35, 304, 296, 252, 330, 62, 108, 172, 375, 263, 370, 359, 293, 9, 69, 43, 61 }

    393

    Returns: 35

  19. { 9, 194, 285, 486, 192, 924, 885, 311, 900, 586, 324, 614, 773, 124, 391, 689, 951, 606, 112, 191, 542, 408, 300, 38, 220, 308, 707, 563, 82, 799, 94, 148, 472, 232, 135, 675, 348, 209, 592, 611, 669, 526, 833, 892, 888, 364, 233, 607, 844, 235 }

    962

    Returns: 32

  20. { 4, 7, 2, 6, 2, 2, 6, 5, 8, 7, 3, 6, 3, 8, 7, 1, 8, 2, 7, 2, 2, 2, 8, 7, 4, 6, 8, 8, 7, 7, 7, 8, 7, 6, 1, 6, 5, 2, 5, 8, 5, 3, 3, 3, 5, 7, 4, 3, 1, 6 }

    8

    Returns: 39

  21. { 168, 278, 377, 304, 224, 391, 135, 134, 73, 387, 371, 377, 373, 22, 338, 119, 248, 117, 371, 50, 372, 285, 344, 38, 358, 320, 55, 46, 175, 324, 45, 317, 129, 238, 310, 3, 352, 192, 251, 290, 131, 222, 361, 383, 110, 238, 27, 308, 196, 270 }

    395

    Returns: 37

  22. { 52, 657, 624, 524, 18, 430, 170, 683, 244, 703, 396, 139, 701, 329, 377, 49, 327, 599, 319, 26, 69, 267, 108, 388, 86, 505, 144, 638, 279, 701, 494, 561, 430, 68, 446, 278, 90, 671, 523, 259, 211, 86, 23, 265, 210, 723, 440, 479, 556, 247 }

    736

    Returns: 32

  23. { 178, 92, 135, 58, 185, 9, 144, 73, 37, 113, 65, 160, 121, 185, 74, 145, 103, 97, 82, 47, 121, 106, 99, 20, 76, 164, 116, 102, 121, 89, 143, 72, 178, 79, 134, 103, 19, 156, 92, 161, 171, 37, 36, 105, 57, 94, 186, 156, 147, 40 }

    191

    Returns: 39

  24. { 695, 168, 506, 26, 772, 15, 632, 292, 360, 287, 447, 221, 69, 813, 252, 731, 219, 798, 628, 45, 266, 13, 355, 126, 484, 249, 450, 534, 660, 668, 109, 373, 131, 796, 355, 258, 345, 622, 543, 690, 800, 475, 794, 8, 525, 685, 737, 766, 93, 100 }

    828

    Returns: 34

  25. { 83, 67, 86, 166, 67, 105, 111, 161, 99, 55, 24, 86, 16, 64, 164, 111, 14, 82, 44, 164, 81, 112, 120, 100, 135, 30, 102, 68, 125, 160, 117, 70, 71, 77, 43, 116, 111, 31, 125, 77, 157, 22, 14, 69, 109, 36, 72, 136, 64, 132 }

    170

    Returns: 36

  26. { 28, 146, 116, 258, 274, 229, 16, 6, 115, 59, 112, 314, 108, 89, 190, 323, 88, 75, 137, 91, 155, 11, 144, 178, 33, 255, 42, 231, 249, 81, 309, 299, 261, 236, 143, 145, 179, 189, 130, 186, 136, 124, 192, 173, 105, 249, 136, 239, 100, 127 }

    329

    Returns: 30

  27. { 145, 383, 156, 20, 235, 17, 177, 301, 832, 424, 306, 12, 607, 828, 602, 532, 566, 81, 816, 708, 351, 693, 808, 232, 403, 211, 796, 258, 288, 121, 478, 157, 200, 781, 721, 350, 236, 856, 767, 830, 604, 871, 698, 458, 295, 350, 567, 163, 65, 426 }

    898

    Returns: 31

  28. { 931, 737, 937, 341, 170, 453, 729, 759, 29, 865, 341, 92, 807, 458, 462, 408, 449, 239, 234, 808, 618, 424, 181, 884, 915, 849, 234, 66, 739, 989, 992, 864, 797, 738, 626, 324, 558, 792, 799, 406, 352, 428, 706, 159, 677, 234, 924, 455 }

    1000

    Returns: 35

  29. { 315, 392, 819, 501, 124, 669, 494, 971, 81, 61, 342, 132, 373, 225, 858, 816, 359, 814, 896, 817, 232, 250, 822, 697, 149, 156, 408, 456, 448, 916, 722, 708, 85, 173, 538, 291, 705, 712, 771, 647, 191, 157 }

    1000

    Returns: 27

  30. { 961, 582, 713, 445, 582, 264, 384, 562, 227, 38, 942, 367, 382, 616, 515, 584, 177, 331, 392, 726, 384, 894, 98, 128, 359, 32, 465, 207, 386, 50, 279, 668, 344, 664, 359, 661, 938, 139, 846 }

    1000

    Returns: 25

  31. { 346, 237, 595, 605, 536, 481, 150, 773, 279, 234, 942, 407, 948, 384, 911, 992, 87, 906, 54, 735, 997, 720, 739, 941, 593, 339, 639, 596, 95, 977, 9, 512, 631 }

    1000

    Returns: 25

  32. { 1, 3, 2, 1, 2, 2, 1, 3, 3, 3, 2, 1, 3, 2, 3, 1, 2, 3, 3, 2, 2, 2, 2, 1, 3, 1, 2, 3, 2, 2, 3, 2, 1, 1, 3, 1, 3, 3, 1, 2, 1, 1, 1, 1, 3, 1, 2, 3, 3, 2 }

    3

    Returns: 39

  33. { 3, 1, 1, 5, 2, 4, 5, 5, 1, 4, 3, 4, 5, 1, 1, 4, 1, 5, 4, 1, 4, 5, 1, 5, 2, 5, 4, 2, 2, 5, 5, 3, 4, 1, 2, 5, 1, 4, 2, 4, 1, 2, 3, 5, 4, 5, 4, 3, 2, 5 }

    5

    Returns: 38

  34. { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    3

    Returns: 10

  35. { 10, 7, 8, 6, 2, 5, 1, 8, 3, 5, 6, 9, 2, 3, 7, 5, 9, 2, 4, 3, 2, 3, 7, 2, 4, 3, 4, 9, 2, 7, 9, 10, 8, 10, 1, 8, 8, 5, 3, 7, 4, 3, 4, 3, 5, 6, 3, 2, 10, 5 }

    262

    Returns: 1

  36. { 10, 7, 8, 6, 2, 5, 1, 8, 3, 5, 6, 9, 2, 3, 7, 5, 9, 2, 4, 3, 2, 3, 7, 2, 4, 3, 4, 9, 2, 7, 9, 10, 8, 10, 1, 8, 8, 5, 3, 7, 4, 3, 4, 3, 5, 6, 3, 2, 10, 5 }

    261

    Returns: 2

  37. {1, 1, 1, 7, 7, 7 }

    8

    Returns: 4

  38. {1 }

    1

    Returns: 1

  39. {1, 15, 1, 15, 1, 15, 1, 15, 1, 15 }

    15

    Returns: 10

  40. { }

    1

    Returns: 0

  41. {5, 5, 5, 5, 5, 5 }

    10

    Returns: 3

  42. {1, 13, 12, 2 }

    13

    Returns: 4

  43. {1, 7, 1, 7, 1, 7 }

    8

    Returns: 3

  44. {7, 7, 7, 1, 1, 1 }

    8

    Returns: 4

  45. { }

    10

    Returns: 0

  46. {3, 3, 1, 4 }

    4

    Returns: 3

  47. {6, 7, 1 }

    7

    Returns: 3

  48. {5 }

    10

    Returns: 1

  49. { }

    20

    Returns: 0

  50. {1, 7, 1, 7 }

    8

    Returns: 2

  51. {6, 2, 6, 2 }

    6

    Returns: 4

  52. {30, 50, 20 }

    50

    Returns: 3

  53. {1, 4, 2, 3 }

    4

    Returns: 4

  54. {1, 9, 1, 9, 1, 9 }

    10

    Returns: 3

  55. {4, 4, 3, 3 }

    7

    Returns: 3

  56. {5, 5, 1, 1 }

    6

    Returns: 3

  57. {8, 9, 2 }

    10

    Returns: 3

  58. { }

    2

    Returns: 0

  59. {3, 5, 7 }

    8

    Returns: 2

  60. {2, 5, 3, 4 }

    7

    Returns: 2

  61. {2, 1, 2, 1 }

    2

    Returns: 4

  62. {1, 7, 1, 7, 1, 7 }

    7

    Returns: 6

  63. {1, 2, 1 }

    2

    Returns: 3

  64. {3, 5, 1, 4, 6, 2 }

    6

    Returns: 5

  65. {4, 5, 5, 3 }

    9

    Returns: 2

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: