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

Question

我们有两个特定大小的房间(我们称之为体积)。我们有很多盒子，必须放在两个房间里。盒子有一定的尺寸，我们不能将任何盒子堆叠在一起。我们的目标是使用回溯算法最大化两个房间中盒子的数量。请问有什么建议吗？

Answer 1

我想我的建议是将其视为树或图结构中的搜索问题。你需要做的就是不断尝试不同的路径并保存“最佳解决方案”。然而，这最终可能会尝试所有的可能性，并且时间复杂度为 O(n!)。因此，我建议您使用某种修剪或逻辑，以免出现这种情况。即 Alpha-Beta 或一旦超过某些规范就不再使用路径。