Load the Delivery Truck
EasyGreedy
Problem
A warehouse has several kinds of boxes. boxTypes[i] = [count, unitsPerBox] means there are count boxes of kind i, each holding unitsPerBox items.
A truck can carry at most capacity boxes (of any kinds). Return the maximum total number of items it can carry.
Example 1
- Input:
- boxTypes = [[1, 3], [2, 2], [3, 1]], capacity = 4
- Output:
- 8
Take the 3-item box, both 2-item boxes and one 1-item box: 3 + 4 + 1 = 8.
Example 2
- Input:
- boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]], capacity = 10
- Output:
- 91
All five 10-item boxes, all three 9-item boxes and two 7-item boxes: 50 + 27 + 14.
Constraints
- 1 ≤ boxTypes.length ≤ 1000
- 1 ≤ count, unitsPerBox ≤ 1000
- 1 ≤ capacity ≤ 10^6
Hint
Show the first hint
Every box takes the same one slot on the truck. What makes one box better than another?
Walkthrough
How to approach it
01Clarify before coding
- Do boxes have different sizes or weights? No: each takes exactly one of the capacity slots.
- Can capacity exceed the total number of boxes? Yes; then take everything.
- Can a box be split? No, but since all boxes cost one slot, splitting never matters.
02Brute force
Treat it as a 0/1 knapsack over individual boxes with weight 1 and value unitsPerBox, using DP over capacity.
Cost: O(total boxes · capacity), up to 10^6 · 10^6: impossible.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.