converge_optimization/packs/bin_packing/
solver.rs

1//! Solver for Bin Packing pack
2
3use super::types::*;
4use converge_pack::gate::GateResult as Result;
5use converge_pack::gate::{ProblemSpec, ReplayEnvelope, SolverReport};
6
7/// First-Fit Decreasing heuristic
8pub struct FirstFitDecreasingSolver;
9
10impl FirstFitDecreasingSolver {
11    pub fn solve(
12        &self,
13        input: &BinPackingInput,
14        spec: &ProblemSpec,
15    ) -> Result<(BinPackingOutput, SolverReport)> {
16        // Sort items by size descending, keeping original indices
17        let mut indexed_items: Vec<(usize, f64)> =
18            input.items.iter().copied().enumerate().collect();
19        indexed_items.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
20
21        let mut bins: Vec<Vec<usize>> = Vec::new();
22        let mut bin_remaining: Vec<f64> = Vec::new();
23
24        for (item_idx, item_size) in indexed_items {
25            // Find first bin that fits
26            let mut placed = false;
27            for (bin_idx, remaining) in bin_remaining.iter_mut().enumerate() {
28                if *remaining >= item_size {
29                    bins[bin_idx].push(item_idx);
30                    *remaining -= item_size;
31                    placed = true;
32                    break;
33                }
34            }
35            if !placed {
36                bins.push(vec![item_idx]);
37                bin_remaining.push(input.bin_capacity - item_size);
38            }
39        }
40
41        let bins_used = bins.len();
42        let output = BinPackingOutput { bins, bins_used };
43
44        let replay = ReplayEnvelope::minimal(spec.seed());
45        let report = SolverReport::optimal("first-fit-decreasing-v1", bins_used as f64, replay);
46
47        Ok((output, report))
48    }
49}
converge_optimization/packs/bin_packing/solver.rs

converge_optimization/packs/bin_packing/
solver.rs
