"Loose" 装箱算法

Question

完全想不出该怎么称呼它，所以我的谷歌搜索也出现问题...

我正在做一些类似于基本 bin packing problem 的事情，但有一些改动让我感到困惑。

箱子的数量始终为 3，并且所有 3 个箱子的尺寸始终相同（等于所有项目尺寸总和的 1/3）
每件物品都必须放入垃圾箱
物品可以 "fragmented" 放入多个连续的箱子中，如果它们不能完全放入一个箱子中。 最小化这个。

根据这三个标准（尤其是 3），我不确定问题是否不再是 NP-hard，但是第四个标准使这成为我所说的 "loose" 问题。

不必严格执行垃圾桶大小。如果一个项目要 "overstuffed" 进入一个垃圾箱，比如说，垃圾箱大小的 10%，那很好，但前提是它可以容纳整个项目（不要为零散的项目过度填充）。

这仍然是一个结构化问题，还是我把我的标准搞得一团糟，以至于它几乎无法再解决了？

如果你很好奇，我正在使用它来呈现许多（或少数）类别（items) 包含许多（或少数）链接。

目标语言是 PHP，但目前最好使用伪代码。

Answer 1

为了未来的访客，我想我会回答我自己的问题...

Loop through items largest to smallest
Does it fit wholly (overstuffing ok) in the first open bin? ...Yes
    Place it
...No
    Does it fit wholly (overstuffing ok) in the next bin? ...Yes
        Place it
    ...No
        Does it fit wholly (overstuffing ok) in the last bin? ...Yes
            Place it
        ...No
            //Place in first open bin, expecting a fragmentation
            Place x "units" of item until bin size reached (no overstuffing)
            Place y "units" of item until bin size reached (no overstuffing), starting at index x into item
            If x+y is still less than item size, place rest in last bin.

如果递增 bin 导致索引越界，它只会将其视为 "no"。可能不是最简洁的实现，但到目前为止它一直对我很好。显然，这种方法对于 3 个 bin 是固定的，但我想它可以合理地扩展到更多（有限）bin。

"Loose" 装箱算法

"Loose" Bin Packing Algorithm

algorithm

bin-packing