空间（槽）优化算法

Question

我将直接从示例开始：

在游戏中，玩家将使用一个袋子来存放他们的物品（物品具有可变尺寸），并且袋子也具有可变尺寸。

在一个 8x15 个插槽的袋子中，我需要插入一个占用 2x2 个插槽的项目，我可以搜索空间来实际检查是否有足够的空间来存储该项目 - 这很容易，但是，如果我没有足够的空间怎么办是否有空间存储所请求的物品？这才是真正的问题。

我正在尝试找到一种方法来实际重新排列当前包中的所有当前项目，以便为新项目释放空间。

有什么算法可以帮助我做到这一点吗？

编辑

规则：

1. 我无法取出包中现有的任何物品，只能重新排列它们，以便在空间不足时存放新物品。

Answer 1

我认为不幸的是这是一个 NP 难问题，但你可以使用贪心近似算法。近似算法的工作原理如下：

• 按物品数量降序对所有物品进行排序。
• 遍历列表并尝试将当前项目放置在任何位置
• 如果在任何时候当前物品无法安装在任何地方，则确定该物品无法拾取。
• 如果所有部件都已安装，则确定该物品可以拾取。

这是基于这样的直觉：较大的部件比较小的部件“更难”放置。如果大多数物品都是 1x1，您可以做的另一件事是暴力解决方案，这在如此小的库存中是相当可行的。这将按如下方式工作：

• 尝试当前作品的每个位置（它仍然适合）以及每个这样的位置：
• 对下一个未定位的部件执行此操作。

这总是会解决您的问题，但速度较慢（尽管更准确）。可以通过省略每一个 1x1 块，然后将它们放置来改进该算法。