1

我使用 BinPack 问题的特殊变体。我使用一种简单的算法 atm,所以我想知道如何调用它来进行一些初步研究。或者有谁知道如何将这个问题减少到已知的问题?


问题:有特定数量和大小的项目 I 和箱 B。

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

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

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

每个箱子都必须装满物品或物品的一部分,以便完全装满。s(b,i)是在 b 中的 i 部分的大小,如果不是,则为 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)
4

1 回答 1

1

最后!

它被称为具有大小保持碎片的装箱(BP-SPF)

有这篇论文

使用项目碎片包装的近似方案 Omer Yehezkely (2006 年 11 月)

于 2013-05-06T12:31:11.320 回答