最小化更改的碎片整理

Question

最小化更改的碎片整理

3

我需要设计一个算法进行简单的碎片整理，但要具有“最小更改量”的特性。假设我有三个容器，容量为10，并且它们中包含以下物品：

Container 1: 2 3 3
Container 2: 4 4
Container 3: 1 5 1 1

所有容器都已经填满了8/10。现在我想放置一个大小为3的下一个物品 - 总体剩余容量为6，但是没有一个容器有3个空闲容量。虽然有多种可能的解决方案进行碎片整理，但我需要一种算法，能够找到解决方案，其中第一个容器中大小为2的物品将被放置在其他地方，因此新的物品可以放入容器1，因为这种解决方案只需要进行一次更改（而不是替换来自容器3的两个物品）。所需结果应该是：

Container 1: 3 3 3(new item)
Container 2: 4 4 2(moved from Container 1)
Container 3: 1 5 1 1

我已经做了一些研究，但我找到的要么是背包问题，要么是Buddy算法，但我不确定这是否真的是我要找的。

你们中的任何一个能帮助我设计尽可能简单的算法吗？我正在解决这样一种情况：我将拥有少量大容器和大量物品，因此枚举所有可能性并不是很优化。

非常感谢！

更新：只是为了明确我的问题 - 确定是否可以通过仅进行一次更改来解决问题并不是问题。问题在于如何在“一次移动”不可行时找到最小的替换次数。

- Marek Galinski

所有的容器大小一定相同吗？ - mhum

不，它们不是。但是尺寸已经给定，我无法即时修改它们。 - Marek Galinski

你能按照物品大小对容器进行排序吗？ - גלעד ברקן

我可以按照自己的意愿对容器进行排序。容器的顺序完全不重要。 - Marek Galinski

我不确定你的例子是否有效。你提出的解决方案是将2从容器1移动到容器2，然后将3放在容器1中。但是，从容器3移动单个1，然后将3放在容器3中，这样不是更"快"吗？你只需要重新定位1个单位而不是2个。 - Mr. Llama

@Mr.Llama，在我的情况下，我不在乎我移动大小为2的物品还是大小为1的物品。我仍然只移动一个物品，这才是最重要的。 - Marek Galinski

2个回答

0

如果这些容器是从头开始构建的，您可以添加状态来表示哪个容器最不满，并始终将下一个项目放在那里。

如果您可以将容器内的大小移除到容器外部，则可能会变得更简单。

仅供参考。

- Aaditya Kalsi

但是这并没有解决这样一个情况，即使将新数量放入最少填充的容器中，仍然可能存在一些分段，这将不允许新项目放置在任何地方，尽管整体可用容量足够大。此外，在我的使用情况下，物品的数量可能会增长。我正在寻找一个解决方案，它将采取“现状”并找到最佳的碎片整理方法。谢谢你的努力 :) - Marek Galinski

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mhum · Accepted Answer

这不是对问题的回答，但是太长了不能作为评论。如此陈述的问题是NP完全问题（一旦我们适当地将其更改为决策问题），可以从PARTITION问题中简化得出。

设x₁，x₂，...，x_n是PARTITION问题的实例。为了表示方便，让我们把x₁取为x的最小值，并且让W为所有x的总和。此外，为了简单起见，让我们假设W是偶数。

我们构造一个该问题的实例来编码我们的PARTITION实例，具体如下。我们有三个容器，大小分别为W、W/2-x₁和x₁。最初，第一个容器包含大小为x₁、x₂、...、x_n的项目，另外两个为空。要插入的新项目的大小为W/2。我们观察到，如果原始的PARTITION问题有解，则可以将此新项目插入这些容器中。

编辑后添加（更多证明细节）

首先，我们假设我们有原始PARTITION问题的解决方案，即：将x分成两个子集S₁和S₂，使得每个子集中x的总和都等于W/2。假设S₁包含x₁，即最小元素。然后，我们可以将x₁移动到第三个容器中，将S₁的所有其他元素移动到第二个容器中，从而为新项目留下W/2的空间。

接下来，假设我们有一种将新的W/2大小元素插入这些容器的方法。通过检查，唯一的方法是在第一个容器中为其腾出空间；而唯一的方法是通过移动价值恰好为W/2的物品来实现这一点（因此，在第一个容器中留下价值恰好为W/2的物品）。显然，这定义了将原始项目集拆分为两个子集的方式，使得每个子集的大小都为W/2。

现在，仅因为这个问题是NP完全问题，并不意味着一切都失去了。这只是意味着如果你认为你已经想出了一个能够在多项式时间内解决所有实例的解决方案，那么你应该检查一下你的工作。你将看到的实例类型的结构（例如：“大容器数量少，其中有大量物品”）可能有助于指导有用的启发式搜索。