回溯算法，以最大化两个房间中的盒子数量

Question

我们有两个特定大小的房间（称之为体积）。我们必须在两个房间中放一些盒子。这些盒子有一定的尺寸，我们不能将任何盒子相互堆叠。我们的目标是使用回溯算法来最大化两个房间中的盒子数量。有什么建议吗？

Answer 1

我想我的建议是将其视为树或图结构中的搜索问题。您需要做的是继续尝试不同的路径并保存“最佳解决方案”。但是，这最终可能会尝试所有可能，并且为O（n！）。因此，我建议您使用某种修剪或逻辑，以免发生这种情况。即Alpha-Beta，或者一旦路径超出某些规格，就不要继续使用。