4

我将直接从示例开始：

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

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

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

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

编辑

规则：

  1. 我无法移除包中的任何现有物品，如果没有足够的空间，只需重新排列它们以便存储新物品。
4

1 回答 1

1

我认为不幸的是这是一个 NP 难题，但您可以使用贪婪逼近算法。近似算法可以如下工作：

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

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

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

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

于 2012-08-27T17:01:06.323 回答