DSA Factory
Free lessonsGreedy · Stage 0 · Take the best now · Step 4

Maximum units on truck

Load boxes with the highest units per box first until the truck is full. About 8 minutes.

Filling the truck

You run a delivery truck. Each box type comes with a number of boxes and a number of units in each box. The truck can hold only so many boxes, and you want to carry the most units in total.

Since every box takes the same space, the ones packed with more units are always better to load first.

Density rule: a box with 10 units is always better than a box with 5.
Sort descending: put the box types with the most units per box first.
Truck holds 4 boxes · box types sorted by units per box, best first
units/boxboxestake
type A
3
1
1
type B
2
2
type C
1
3
space
3
units
3

Type A is worth 3 per box. Take all 1 of them.

Move 1 of 3

The greedy loading loop

At each step, look at the space left in the truck. If the best box type has 5 boxes and the truck has room for 3, take 3 and stop. If the truck has room for 8, take all 5 and carry on with the next type.

Stop as soon as the space reaches zero.

Take the smaller: of the space left and the boxes available.
Reduce the space: by what you took, until it reaches 0.
In code
boxes.sort(key=lambda x: x[1], reverse=True)
total = 0
for count, units in boxes:
    take = min(space, count)
    total += take * units
    space -= take
    if space == 0:
        break
return total
Quick check

Box type A has 2 boxes with 3 units each. Box type B has 5 boxes with 1 unit each. Truck holds 3 boxes. How many units?

  1. A7 units (all 2 of A, plus 1 of B)
  2. B6 units
Show the answer

7 units (all 2 of A, plus 1 of B). Take 2 boxes of A (2×3 = 6 units), leaving 1 space for B (1×1 = 1 unit). Total = 6 + 1 = 7.

Your problem

Maximum units on truck

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxes, where boxes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]. You are also given an integer space, which is the maximum number of boxes that can be put on the truck. Return the maximum total number of units that can be put on the truck.

Example
boxes = [[1, 3], [2, 2], [3, 1]], space = 4 → 8

1 ≤ boxes.length ≤ 1,000 · 1 ≤ numberOfBoxes_i, numberOfUnitsPerBox_i, space ≤ 1,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding