bin_packer_3d

该crate使用三维装箱算法解决“将较小的箱子装入较大的箱子”的问题。

该算法通过利用首次适应递减（FFD）贪婪策略和旋转优化，将所有项目正交地装入最少数量的箱子中。

使用方法

    use bin_packer_3d::bin::Bin;
    use bin_packer_3d::item::Item;
    use bin_packer_3d::packing_algorithm::packing_algorithm;

    let deck = Item::new("deck", [2, 8, 12]);
    let die = Item::new("die", [8, 8, 8]);
    let items = vec![deck, deck, die, deck, deck];

    let packed_items = packing_algorithm(Bin::new([8, 8, 12]), &items);
    assert_eq!(packed_items, Ok(vec![vec!["deck", "deck", "deck", "deck"], vec!["die"]]));

局限性

该算法解决的是3D装箱问题的约束版本。因此，存在以下局限性

• 我们要装箱的项目和我们要装入的箱子都限于长方体形状。

• 我们要装箱的项目可以沿任何方向旋转，但每个边必须与对应箱子的边平行。

• 作为一个NP-Hard问题，该算法不试图找到最优解，而是使用一个时间复杂度为O(n^2)的近似解。

致谢

当装箱的项目小于箱子边长的一半时，该算法利用了Martello（1997）在论文“三维装箱问题”（第257页）中提出的旋转优化方法：“The Three-Dimensional Bin Packing Problem”（https://www.jstor.org/stable/pdf/223143.pdf）