Cargo Container Loading

0-1 Knapsack Problem

A shipping company must decide which cargo items to load into a container with a strict weight limit. Each item has a revenue value and a weight. The goal is to maximize total value without exceeding the container’s capacity — a classic instance of the 0-1 Knapsack Problem.

The Problem

Selecting cargo to maximize revenue under weight constraints

A freight company is loading a standard shipping container onto a cargo vessel. The container has a maximum weight capacity of W tons. At the warehouse, there are n cargo items awaiting shipment, each with a known value (the revenue generated by shipping it) and a known weight. Every item is either loaded entirely or left behind — partial loading is not allowed. This is the fundamental 0-1 decision.

The objective is to maximize total revenue from the selected cargo items while ensuring the combined weight does not exceed the container’s capacity. Although the problem statement is deceptively simple, it is NP-hard (weakly) — no known algorithm can solve all instances in time polynomial in n alone. However, the pseudo-polynomial Dynamic Programming approach makes it tractable for moderate capacities.

The 0-1 Knapsack Problem was formalized by Dantzig (1957) and is one of Karp’s 21 NP-complete problems (1972). It appears throughout logistics, finance, resource allocation, and project selection wherever a binary “take it or leave it” decision must be made under a budget or capacity constraint.

0-1 Knapsack Formulation maximize Σ_i=1..n v_i · x_i // total cargo value
subject to
Σ_i=1..n w_i · x_i ≤ W // total weight ≤ container capacity
x_i ∈ {0, 1} // each item is loaded (1) or not (0)

Where v_i is the value of item i, w_i is its weight, and W is the container capacity.

See full Knapsack theory and all algorithms

Try It Yourself

Load a shipping container for maximum revenue

Container Loading Optimizer

6 Items · 50t Capacity · Click any cell to edit

Container Capacity (tons):

Cargo Manifest

#	Cargo Name	Value ($k)	Weight (t)	Density

Algorithm

Dynamic Programming [exact]

Branch & Bound [exact]

Greedy Density [heuristic]

Container Visualization

Results Comparison

Algorithm	Total Value	Total Weight	Utilization	Items	Time
Select algorithms and click Solve

Select algorithms and click "Solve & Compare All Algorithms" to solve.

The Algorithms

Three approaches from exact to approximate

Dynamic Programming

Exact

Standard bottom-up tabulation. Build a table dp[i][w] representing the maximum value achievable using items 1 through i with capacity w. The recurrence is:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_i] + v_i)
// skip item i | take item i (if w_i ≤ w)

After filling the table, backtrack from dp[n][W] to identify which items were selected. Guarantees optimality.

O(n × W) pseudo-polynomial

Branch & Bound

Exact

Depth-first search over the binary decision tree (take or skip each item). At each node, compute an upper bound by adding the fractional portion of the next item sorted by value density. If the bound does not exceed the best known solution, the subtree is pruned. The greedy solution provides the initial lower bound.

Worst case is exponential, but effective pruning makes it fast in practice, especially when items have diverse value-to-weight ratios.

O(2ⁿ) worst case, fast with pruning

Greedy Density

Heuristic

Sort items by value-to-weight ratio (value density) in descending order. Greedily add items while they fit within the remaining capacity. Simple and fast, but not guaranteed to find the optimal solution — it can miss cases where a heavy high-value item should replace several lighter ones.

O(n log n)

Why It’s More Complex

Real-world cargo loading goes far beyond weight limits

Beyond the Basic Model

Multiple containers — Loading across several containers of different sizes transforms the problem into a multi-dimensional bin packing variant.
3D spatial constraints — Items have length, width, and height; they must physically fit and remain stable when stacked.
Hazardous material segregation — IMO regulations require certain chemical classes to be separated by minimum distances or placed in different containers.
Port-specific regulations — SOLAS VGM requirements mandate verified gross mass; some ports restrict container floor loading (kg/m²).
Container weight distribution — Center of gravity must be balanced to prevent tipping during transit; axle weight limits apply for road transport.
Refrigeration needs — Perishable goods require reefer containers with limited capacity, adding equipment constraints to the model.

Key References

Kellerer, H., Pferschy, U., & Pisinger, D. (2004). “Knapsack Problems.” Springer-Verlag Berlin Heidelberg. Comprehensive monograph covering theory, algorithms, and applications of all knapsack variants.
Martello, S., & Toth, P. (1990). “Knapsack Problems: Algorithms and Computer Implementations.” John Wiley & Sons. Classic reference with detailed algorithm descriptions and computational experiments.

Need to optimize cargo logistics?

From container loading and warehouse allocation to supply chain network design, mathematical optimization transforms operational decisions into measurable savings.

Connect on LinkedIn

Disclaimer

Data shown is illustrative. Cargo item names, values, and weights are representative examples for educational purposes and do not reflect actual shipping rates or commodity weights.