algorithm - 如何减少这种 BinPack 算法？ (它可能被称为 MinBreak-BinFill 之类的东西。)

Question

我使用了 BinPack 问题的一个特殊变体。我使用一种朴素的算法，atm，所以我想知道如何调用来做一些初步研究。或者有人知道如何将这个问题减少到已知的东西吗？

---

问题:有特定数量和尺寸的元素 I 和箱 B。

|I| ∈ ℕ, |B| ∈ ℕ
s : (I ∪ B) → ℕ

所有 item-size 的总和至少是所有 bin 的总和的大小。

∑ _{i∈I} s(i) ≥ ∑ _{b∈B} s(b)

每个箱子都必须装满元素或元素的一部分，以便完全装满。 s(b,i) 是 i 在 b 中的那部分的大小，如果不是，则为 0。

∀ b ∈ B, i ∈ I: s(b,i) ∈ ℕ ∪ {0}
∀ i ∈ I: ∑ _{b∈B} s(b,i) ≤ s(i)
∀ b ∈ B: ∑ _{i∈I} s(b,i) ≥ s(b)

目标是尽量减少填充所有箱子所需的元素部件数量。

numparts = |{ (b,i) ∈ B×I | s(b,i)>0 }|
find min(numparts)

Answer 1

终于!

它被称为带大小保留碎片的装箱 (BP-SPF)。

存在这篇论文

ApproximationSchemesforPackingwithItemFragmentationOmerYehezkely(2006 年 11 月)