Load Crates Onto a Truck for the Most Cargo
Solve this ProblemA truck can carry at most truckSize crates. Crates come in several types: each type has a count (how many crates of that type exist) and the units of cargo each crate of that type holds. You may load any number of crates of each type, up to its count. Find the maximum total units the truck can carry.
Every crate takes one slot, so the only thing that differs is how many units each carries. Sorting the crate types by units per crate and loading the densest ones first is optimal — no table of combinations is needed.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ crateTypes.length ≤ 8; each row is [count, unitsPerCrate] - ◆
1 ≤ count ≤ 20 and 1 ≤ unitsPerCrate ≤ 30 - ◆
1 ≤ truckSize ≤ 200 — the truck holds at most truckSize crates in total, regardless of type - ◆
You may take any number of crates of each type, from none up to its count. Return the maximum total units of cargo the truck can carry
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Bounded Knapsack Table Over Truck Space
BruteTreat the truck's crate slots as the capacity and build a table where best[r] is the most cargo that r slots can hold using the crate types seen so far. For each crate type, update the table from the fullest truck down to the emptiest (so each type is only counted once): for every r, try taking 1, 2, … up to count crates of this type, each adding its units on top of best[r − take]. Correct for any values, but it works through every combination of type, slot count and quantity.
O(types × truckSize × count)O(truckSize)1class Solution {
2 public int maxCargoUnits(int[][] crateTypes, int truckSize) {
3 int[] best = new int[truckSize + 1];
4 for (int[] type : crateTypes) {
5 int count = type[0], units = type[1];
6 for (int room = truckSize; room >= 1; room--) {
7 for (int take = 1; take <= count && take <= room; take++) {
8 best[room] = Math.max(best[room], best[room - take] + take * units);
9 }
10 }
11 }
12 return best[truckSize];
13 }
14}Optimal — Sort by Units per Crate and Load the Densest First
OptimalEvery crate takes exactly one slot, so the only thing that matters is how many units each slot carries. Sort the crate types by units per crate, highest first, and load greedily: for each type take as many crates as still fit (the smaller of its count and the remaining slots), add their units, and stop as soon as the truck is full. A slot filled with a denser crate can never be improved by swapping in a less dense one.
O(types log types)O(types)1class Solution {
2 public int maxCargoUnits(int[][] crateTypes, int truckSize) {
3 int[][] sorted = crateTypes.clone();
4 Arrays.sort(sorted, (a, b) -> b[1] - a[1]);
5 int total = 0, room = truckSize;
6 for (int[] type : sorted) {
7 if (room == 0) break;
8 int take = Math.min(room, type[0]);
9 total += take * type[1];
10 room -= take;
11 }
12 return total;
13 }
14}