How the solver works

Algorithm approach

The solver uses a greedy search with backtracking that explores the solution space systematically in three stages.

1. Grouping and pruning

Cans are first grouped by specification (110 g, 227 g, 450 g) and sorted by fuel level within each group. The algorithm then iterates through every valid combination of how many cans of each size to keep, pruning branches where:

• the combined capacity is insufficient to hold all fuel, or
• the combined empty weight already exceeds the best solution found so far.

2. Allocation with minimal transfers

For each candidate set of cans to keep, the solver solves a secondary problem: move fuel from donors (discarded cans, or kept cans that are over capacity) to recipients (kept cans with spare capacity) while minimizing, in order:

1. the number of transfer operations, and
2. the total grams transferred.

This uses a greedy heuristic for an initial feasible solution, then a depth-first search with memoization under a progressively increasing edge budget, so plans with the fewest transfers are found first.

3. Lexicographic optimization

Solutions are compared with a three-part score:

type Score = [emptyWeight, transferCount, totalTransferred]

Comparison is lexicographic: prefer lower empty weight, then fewer transfers, then less total fuel moved.

Time complexity

Worst case

• Outer loop: O(lenA × lenB × lenC) over the counts of each can type, roughly O(n³/27) for n cans evenly distributed.
• Allocation subproblem: O(D × R × E) where D is the number of donors, R the number of recipients, and E the edge budget.
• Memoization removes most repeated subproblems.

Overall O(n³ × D × R × E) in the worst case, but early pruning eliminates most branches and a workload estimator caps total work.

Practical performance

A workload estimate acts as a complexity guard:

workload = (lenA + 1) × (lenB + 1) × n
if (workload > 5_000_000) throw Error

This allows roughly 300 cans of mixed sizes, more when one size dominates, and gives sub-second results for typical inputs of 10 to 50 cans.

Space complexity

• O(n²) for the transfer matrix and the plan representation.
• The memoization cache is bounded in practice by the workload limit.

Performance characteristics

Fast paths

• All cans empty: O(n), returns an empty plan immediately.
• A single can size: O(n²), simplified grouping.
• Under-filled cans: O(n²), minimal transfers needed.

Slow paths

• Many cans near capacity, which requires extensive transfer exploration.
• Mixed sizes with tight constraints where all three sizes appear in the solution.
• A high donor-to-recipient ratio, which multiplies transfer combinations.

Optimization strategies

1. Early termination when empty weight exceeds the current best.
2. Capacity-based pruning to skip impossible combinations immediately.
3. Greedy initialization, then refinement.
4. Memoization of allocation subproblems keyed by state signature.
5. Edge budget progression, trying simple plans before complex ones.

Limitations

Input size

About 300 cans for mixed scenarios, enforced by the workload limit. Performance degrades noticeably beyond about 200 cans.

Optimality guarantees

The choice of which cans to keep is globally optimal. The transfer plan within that choice is locally optimal and may not explore every possible transfer ordering.

Assumptions

• Fuel values are non-negative.
• Transfers are instantaneous and lossless.
• Empty weight is fixed per can specification.
• Only three can sizes are supported.

Future improvements

1. Branch and bound with tighter lower bounds.
2. A dynamic programming formulation for transfer allocation.
3. Parallel exploration of can combinations across workers.
4. Incremental solving as inputs change.
5. Better initial heuristics to shrink the search.

References

The allocation subproblem is related to bin packing, the transportation problem, and capacity-constrained bipartite assignment. The solver trades guaranteed optimality of the transfer schedule for practical performance, giving excellent results for real-world backpacking scenarios in well under a second.