我使用 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)