1

我想解决一个 3 维背包问题。

我得到了许多具有不同宽度、高度、长度和价值的盒子。我有一个指定的空间，我想把盒子放在那个空间里，这样我就能得到最优的利润。我想使用蛮力来做到这一点。

我正在用 Java 编程。我试图用递归来做到这一点，所以：

public void solveBruteforce(double freeX, double freeY, double freeZ) {
   for(int i = 0; i < numOfBoxes; i++) {
      for(int j = 0; j < BoxObject.numOfVariations; j++) {
         if(possible to place box) {
            place(box);
            add(value);
            solveBruteforce(newX, newY, newZ);
         }
      }
   }
   remove(box);
   remove(value);
}

但我会遇到每行都有不同的自由 x、y 和 z 的问题。

有人可以帮我找到另一种方法吗？

4

1 回答 1

0

首先，使用八叉树来跟踪空间中事物的位置。占用树是一个 3D 4 度树，每个节点都有占用标志，将您的空间划分为一个可以有效搜索的地方。如果您想使用某种启发式搜索来放置框，即使您正在尝试所有可能性，这也会很有用。它可以缩短禁止（拥挤）的展示位置。

蛮力需要很长时间。但如果这就是你想要的，你需要定义一个排序来尝试排列排列。

由于您将需要多次迭代，因此递归并不是那么好，因为您会遇到堆栈溢出。

一个初稿的替代方案将涉及一个贪心算法。拿一个让你的利润最大化的盒子（比如说，最大的），把它放好，然后拿下一个最大的盒子，然后找到最适合它的盒子，以此类推。

但是，假设您想尝试所有可能的组合：

def maximize_profit(boxes,space):
    max_profit = 0
    best_fits = list()
    while(Arranger.hasNext()):
        a_fit,a_profit = Arranger.next(boxes,space)
        if (a_profit == max_profit):
            best_fits.append(a_fit)
        elif (a_profit > max_profit):
            max_profit = a_profit
            best_fits = [ a_profit ]
    return best_fits, max_profit

有关如何定义排列器的想法，请考虑从#{space} 可能性中选择#{box} 槽，尊重具有相同wrt 对称性的排列。或者，也许“洪水填充”方法会给你一些想法。

于 2012-01-16T10:22:02.823 回答