在 Java 中使用暴力破解 3D 背包

Question

我想解决一个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 的问题。

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

Answer 1

首先，使用八叉树来跟踪事物在空间中的位置。占用树是一棵 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} 插槽，尊重与对称性相同的排列。或者，也许“洪水填充”方法会给你一些想法。