-1

想不起来怎么称呼这个，所以我的谷歌搜索也很短......

我正在做一些类似于基本的垃圾箱包装问题的事情，但有一些改变让我感到困惑。

  1. bin 的数量始终为 3，并且所有 3 始终是相同的尺寸（等于所有项目尺寸总和的 1/3）
  2. 每件物品都必须放在垃圾箱中
  3. 如果项目不能完全放入一个容器中，则它们可以被“分割”成多个连续的容器。最小化这个。

有了这三个标准（尤其是第 3 个），我不确定问题是否是 NP 难题了，但是第四个标准使我称之为“松散”问题。

  1. 垃圾箱大小不必严格执行。如果一个项目要被“过度填充”到一个垃圾箱中，比如说，垃圾箱大小的 10%，那很好，但前提是它可以容纳整个项目（不要为零散的项目过度填充）。

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

如果你很好奇，我正在使用它来呈现包含许多（或少数）链接的许多（或少数）类别（项目）的 3 列（箱）。

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

4

1 回答 1

0

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

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 导致索引超出范围，它只会将其视为“否”。可能不是最整洁的实现，但到目前为止它一直对我很好。显然，这种方法对于 3 个箱子是固定的，但我想它可以合理地扩展到更多（有限）箱子。

于 2015-01-21T00:54:15.583 回答