在Java中使用bruteforce解决3D背包问题

我想解决一个3-dimesional背包问题。在Java中使用bruteforce解决3D背包问题

我得到了一些不同宽度，高度，长度和价值的盒子。我得到了一个特定的空间，我想把这些箱子放进这个空间，这样我就可以获得最佳利润。我想用bruteforce来做。

我使用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上的问题。

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

来源

2012-01-16 Nando

首先，使用八叉树来跟踪事物在空间中的位置。占用树是一个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

有关如何定义的编曲，可考虑从＃{空间}可能性选择＃{盒子}插槽的想法，尊重是安排相同的重量对称。或者，也许一个“洪水填充”方法会给你的想法。

来源

2012-01-16 10:22:02

首先我想感谢你的回答。我知道贪婪的算法，但我不明白你对占据树的看法。是否有另一种方式来做到这一点。或者，如果我将问题的大小缩小到3或4个具有给定长度，高度和宽度的框？ – Nando 2012-01-16 23:02:37

@ user1110725八叉树每次只检查每个占用点。只需要检查它们的日志（点）。嗯，如果你想要3或4个盒子，你可以通过只给出x，y，z来完全定义，那么它们将具有最大3个面部大小，并且如果你只允许平行轴布局，那么每个可能的旋转6个框。所以只要这个空间不是那么大，那么这个空间就会比那些有很多位置选择的空间大得多。只要确保你旋转了每个盒子的所有盒子。并通过（如果是4盒）24个订单。此外，谷歌“最佳箱包装”。 – 2012-01-17 13:37:47

在Java中使用bruteforce解决3D背包问题

回答

相关问题