Jungle Expedition Resupply Optimization — Problem Statement & Solution Guide
Problem Description
In a jungle expedition supply chain, cargo planes drop off crates of supplies at designated coordinates. Each crate has a unique identifier and a specific weight. The expedition team needs to determine the optimal way to load the crates onto their vehicles, given the weight capacity of each vehicle. The input will be a 2D array of crates where each crate is represented as an array of two integers, the first integer being the crate's unique identifier and the second integer being the crate's weight. The function should return a 2D array where each sub-array represents the crate identifiers loaded into a vehicle.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Jungle Expedition Resupply Optimization"
WHY DOES IT MATTER?
The 0/1 knapsack pattern captures a broad class of resource allocation problems where items are indivisible and a hard constraint (capacity) must be respected, making it a cornerstone for optimization interviews.
OPTIMIZATION CHALLENGE
The key insight is recognizing overlapping sub‑problems and compressing the 2‑D DP table to a 1‑D array, which cuts space from O(n·C) to O(C) while preserving correctness by iterating capacities in reverse.
REAL-WORLD CONNECTION
In distributed systems, allocating tasks to servers with limited memory mirrors knapsack: each task (crate) has a memory footprint (weight) and the server's RAM is the capacity. Efficient packing improves throughput and reduces latency.
During an interview, write the DP recurrence first, then immediately discuss space compression. This shows you understand both the algorithmic core and practical engineering constraints.
COMPLEXITY AT A GLANCE
O(n·C)O(C)Core Theory — Why This Approach?
The Jungle Expedition Resupply Optimization problem is a classic instance of the 0/1 Knapsack problem. Each crate can either be taken whole or left behind, and the goal is to maximize the total weight (or value) of crates loaded onto a vehicle without exceeding its weight capacity. A naive brute‑force solution enumerates all 2ⁿ subsets, which quickly becomes infeasible as n grows beyond 30 because the exponential time blows up. The optimal paradigm leverages dynamic programming: we build a DP table where dp[i][w] represents the maximum total weight achievable using the first i crates with a remaining capacity w. By iteratively filling this table, we achieve a pseudo‑polynomial solution that runs in O(n·C) time, where C is the vehicle capacity, and O(C) space can be obtained by compressing the table to a one‑dimensional array. This DP approach exploits overlapping sub‑problems and optimal substructure, turning an exponential search into a tractable polynomial one for realistic capacity limits.
Interview Questions on This Problem
Q1How would you modify the solution if each crate also had a monetary value and you needed to maximize total value while respecting the weight capacity?
Introduce a second dimension for value in the DP state, or keep the same DP table but store the maximum value instead of weight for each capacity. The recurrence becomes dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) for each crate, still O(n·C) time.
Q2Can you solve the problem in O(n log n) time if the vehicle capacity is very large compared to the sum of all crate weights?
When total weight sum S is much smaller than capacity C, we can switch to a DP over total weight rather than capacity: dp[v] = minimum weight needed to achieve value v. This runs in O(n·S) which can be sub‑linear in C, and if S is small, the algorithm behaves like O(n log n) after sorting and using a meet‑in‑the‑middle technique.
Q3Explain how you would extend the single‑vehicle solution to handle multiple identical vehicles with the same capacity.
The multi‑vehicle case reduces to a bounded knapsack where each crate can be assigned to at most one vehicle. One approach is to run the single‑vehicle DP repeatedly, each time removing the selected crates, which yields O(k·n·C) for k vehicles. A more efficient method models it as a flow problem or uses DP with an extra dimension for the number of vehicles, achieving O(k·n·C) but with better constant factors.
Examples
Input
[[1, 10], [2, 20], [3, 30]]
Output
[[1, 2], [3]]
Explanation: Step-by-step: with input [[1, 10], [2, 20], [3, 30]] and vehicle capacity 30, we first sort crates by weight in descending order, then we load the heaviest crates first into the vehicles. In this case, we load crate 3 (weight 30) into the first vehicle and crates 1 (weight 10) and 2 (weight 20) into the second vehicle, resulting in the output [[1, 2], [3]].
Input
[[1, 5], [2, 10], [3, 15], [4, 20]]
Output
[[1, 2], [3, 4]]
Explanation: Step-by-step: with input [[1, 5], [2, 10], [3, 15], [4, 20]] and vehicle capacity 20, we first sort crates by weight in descending order, then we load the heaviest crates first into the vehicles. In this case, we load crate 4 (weight 20) into the first vehicle and crate 3 (weight 15) into the second vehicle. Then we load crate 2 (weight 10) into the first vehicle and crate 1 (weight 5) into the second vehicle, resulting in the output [[1, 2], [3, 4]].
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Use dynamic programming with a 1‑D array to compute the optimal weight for each capacity, achieving O(n·C) time and O(C) space.
Brute Force Approach
Enumerate every subset of crates and keep the best that fits within the capacity; this runs in O(2ⁿ) time.
Verified Code Solutions
function solution(crates, capacity) {
crates.sort((a, b) => b[1] - a[1]);
let vehicles = [];
for (let crate of crates) {
let added = false;
for (let vehicle of vehicles) {
let totalWeight = vehicle.reduce((acc, curr) => acc + curr[1], 0);
if (totalWeight + crate[1] <= capacity) {
vehicle.push(crate);
added = true;
break;
}
}
if (!added) {
vehicles.push([crate]);
}
}
return vehicles.map(vehicle => vehicle.map(crate => crate[0]));
}class Solution {
public:
vector<vector<int>> solution(vector<vector<int>>& crates, int capacity) {
sort(crates.begin(), crates.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] > b[1]; });
vector<vector<vector<int>>> vehicles;
for (auto crate : crates) {
bool added = false;
for (auto& vehicle : vehicles) {
int totalWeight = 0;
for (auto c : vehicle) {
totalWeight += c[1];
}
if (totalWeight + crate[1] <= capacity) {
vehicle.push_back(crate);
added = true;
break;
}
}
if (!added) {
vehicles.push_back({crate});
}
}
vector<vector<int>> result;
for (auto vehicle : vehicles) {
vector<int> crateIds;
for (auto crate : vehicle) {
crateIds.push_back(crate[0]);
}
result.push_back(crateIds);
}
return result;
}
};import java.util.Arrays;
public class Solution {
public int[][] solution(int[][] crates, int capacity) {
Arrays.sort(crates, (a, b) -> b[1] - a[1]);
ArrayList<ArrayList<int[]>> vehicles = new ArrayList<>();
for (int[] crate : crates) {
boolean added = false;
for (ArrayList<int[]> vehicle : vehicles) {
int totalWeight = 0;
for (int[] c : vehicle) {
totalWeight += c[1];
}
if (totalWeight + crate[1] <= capacity) {
vehicle.add(crate);
added = true;
break;
}
}
if (!added) {
ArrayList<int[]> newVehicle = new ArrayList<>();
newVehicle.add(crate);
vehicles.add(newVehicle);
}
}
int[][] result = new int[vehicles.size()][];
for (int i = 0; i < vehicles.size(); i++) {
ArrayList<int[]> vehicle = vehicles.get(i);
int[] crateIds = new int[vehicle.size()];
for (int j = 0; j < vehicle.size(); j++) {
crateIds[j] = vehicle.get(j)[0];
}
result[i] = crateIds;
}
return result;
}
}def solution(crates, capacity):
crates.sort(key=lambda x: x[1], reverse=True)
vehicles = []
for crate in crates:
added = False
for vehicle in vehicles:
total_weight = sum([c[1] for c in vehicle])
if total_weight + crate[1] <= capacity:
vehicle.append(crate)
added = True
break
if not added:
vehicles.append([crate])
return [[crate[0] for crate in vehicle] for vehicle in vehicles]function solution(crates, capacity) {
crates.sort((a, b) => b[1] - a[1]);
let vehicles = [];
for (let crate of crates) {
let added = false;
for (let vehicle of vehicles) {
let totalWeight = vehicle.reduce((acc, curr) => acc + curr[1], 0);
if (totalWeight + crate[1] <= capacity) {
vehicle.push(crate);
added = true;
break;
}
}
if (!added) {
vehicles.push([crate]);
}
}
return vehicles.map(vehicle => vehicle.map(crate => crate[0]));
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.