3

编辑：这个问题似乎被称为“切割库存问题”

我需要一种算法，它可以为我提供箱中块的（空间）最佳排列。一种方法是先放入较大的块。但是看看这个算法在这个例子中是如何失败的：

Chunks        Bins
-----------------------------
AAA BBB CC DD (       ) (   )

Algorithm     Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal       (AAACCDD) (BBB)

“最大的优先”不适合 DD。也许它有助于建立这样的表：

Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB

Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB

Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD
4

4 回答 4

3

这基本上是装箱问题的变体。众所周知，这个问题是 NP 难的，所以不要期望为复杂的情况（即有很多对象和 bin）找到一个有效的最优算法。

但是，如果您的对象/箱的数量相对较少，您可能只需使用深度优先搜索详尽地搜索所有可能的组合就可以了。

这很容易实现：只需获取第一个对象，然后递归地重新运行算法，将第一个对象依次放置在每个 bin 中（即从可用 bin 空间中减去对象的大小）。最后，您只需要跟踪迄今为止找到的最佳“解决方案”，并在尝试所有组合后将其作为最终答案返回。

您还可以通过以下方式使该算法算法运行得更快：

  • 将所有大小相等的对象视为等价的
  • 如果你不可能击败当前的最佳解决方案，例如当你已经找到一个完美的匹配时，修剪搜索树（即从一个分支提前返回）

根据对问题大小的评论进行更新

鉴于您看起来有大量的块要处理，您可能需要尝试以下操作：

  • 使用上述详尽搜索来拟合最大的 10-20 个块
  • 使用最大拟合方法分配剩余部分
于 2010-12-23T18:45:08.137 回答
2

Mikera 是对的：这个多重背包问题（装箱问题的一种变体）是NP 难题。

以下是您的一些选择（从我对类似问题的回答中复制）：

  • 蛮力，或者更好的是，分支和约束。无法扩展（根本！），但会为您找到最佳解决方案（尽管可能不是在我们的有生之年）。

  • 确定性算法：按最大大小对块进行排序，并逐个遍历该列表并为其分配最佳剩余位置。这将很快完成，但解决方案可能远非最佳（或可行）。这是一张漂亮的图片，展示了一个可能出错的例子。但是，如果您想保持简单，那就是要走的路。

  • 元启发式，从确定性算法的结果开始。这将在合理的时间内给你一个非常好的结果，比人类想出的要好。根据您给它的时间和问题的难度，它可能是也可能不是最佳解决方案。那里有几个库，例如Drools Planner（开源 java）。

于 2010-12-24T10:14:15.903 回答
1

尚不存在针对此问题的一般最佳算法（请参阅装箱问题）。您可以在维基百科上找到一些不同的方法和/或在谷歌上搜索“装箱问题”，也许“背包问题”也会提供一些帮助。

于 2010-12-23T18:34:34.113 回答
0

Donald Knuth 的Dancing Links算法可以快速找到“精确覆盖”问题的解决方案。

于 2010-12-23T18:44:41.680 回答