碎片整理与最小的变化
Defragmentation with minimum changes
我需要设计一个算法来执行简单的碎片整理，但具有 "minimum amount of changes" 功能。假设我有 3 个容量为 10 的容器，其中包含以下项目：
Container 1: 2 3 3
Container 2: 4 4
Container 3: 1 5 1 1
所有容器都装满了 8/10。现在我想放置下一个大小为 3 的项目 - 总可用容量为 6，但容器的 none 的可用容量为 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 算法，但我不确定，这些是否真的是我要找的。
你们谁能帮我把这个算法设计得尽可能简单吗？我正在解决这样一种情况，即我将拥有少量大容器和大量物品，因此列举所有可能性并不是最佳选择。
非常感谢！
UPDATE 只是为了弄清楚我在问什么 - 确定是否可以通过仅进行一项更改来解决问题是没有问题的。问题是，当 "one single move" 不可能时，如何找到最小替换量。
如果这些容器是从头开始构建的，您可以添加状态来说明哪个容器装得最少，并始终将下一个容器放在那里。
如果可以将容器的大小从容器内移到容器外，这可能会变得更简单。
只是我的 2 美分。
这不是问题的答案，但评论太长了。此处所述的问题是 NP 完全问题（一旦我们适当地将其更改为决策问题），可从 the PARTITION problem 归约。
设 x1, x2, ..., xn 是一个PARTITION 问题的实例。为了记法，让我们将 x1 设为最小的 x 的大小，并令 W 为所有 x 的总和。此外，为了简单起见，我们假设 W 是偶数。
我们构造给定问题的一个实例来编码我们的 PARTITION 实例，如下所示。我们有三个大小为 W、W/2-x1 和 x1 的容器。最初，第一个容器包含大小为 x1、x2、...、xn[=43= 的项目] 而另外两个是空的。要插入的新项目的大小为 W/2。我们观察到当且仅当原始 PARTITION 问题有解时，这个新项目才能插入到这些容器中。
编辑添加（更多证明细节）
首先，我们假设我们有原始分区问题的解决方案，即：将 x 分成两个子集 S1 和 S2 这样每个子集中的 x 的总和等于 W/2。假设 S1 包含最小元素 x1。然后，我们可以将 x1 移动到第三个容器中，并将 S1 的所有其他元素移动到第二个容器中，从而留下 space 的 W/2 在新项目的第一个容器中。
接下来，假设我们有某种方法可以将新的 W/2 大小的元素插入到这些容器中。通过检查，发生这种情况的唯一方法是在第一个容器中为其创建 space ； 可能发生的唯一方法是将正好 W/2 的物品移出（并因此留下正好 W/2 的物品）第一个容器。显然，这定义了将原始项目集拆分为两个子集，使得每个子集的大小为 W/2.
现在，仅仅因为这个问题是 NP 完全的并不意味着一切都丢失了。它只是意味着，如果您认为您已经想出了一个可以在多项式时间内解决所有实例的解决方案，那么您应该检查一下您的工作。您将看到的实例类型的结构（例如："low amount of large containers and huge amount of items in them"）可能有助于指导搜索有用的启发式方法。
我需要设计一个算法来执行简单的碎片整理，但具有 "minimum amount of changes" 功能。假设我有 3 个容量为 10 的容器，其中包含以下项目：
Container 1: 2 3 3
Container 2: 4 4
Container 3: 1 5 1 1
所有容器都装满了 8/10。现在我想放置下一个大小为 3 的项目 - 总可用容量为 6，但容器的 none 的可用容量为 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 算法，但我不确定，这些是否真的是我要找的。
你们谁能帮我把这个算法设计得尽可能简单吗？我正在解决这样一种情况，即我将拥有少量大容器和大量物品，因此列举所有可能性并不是最佳选择。
非常感谢！
UPDATE 只是为了弄清楚我在问什么 - 确定是否可以通过仅进行一项更改来解决问题是没有问题的。问题是，当 "one single move" 不可能时，如何找到最小替换量。
如果这些容器是从头开始构建的，您可以添加状态来说明哪个容器装得最少，并始终将下一个容器放在那里。
如果可以将容器的大小从容器内移到容器外，这可能会变得更简单。
只是我的 2 美分。
这不是问题的答案，但评论太长了。此处所述的问题是 NP 完全问题（一旦我们适当地将其更改为决策问题），可从 the PARTITION problem 归约。
设 x1, x2, ..., xn 是一个PARTITION 问题的实例。为了记法，让我们将 x1 设为最小的 x 的大小，并令 W 为所有 x 的总和。此外，为了简单起见，我们假设 W 是偶数。
我们构造给定问题的一个实例来编码我们的 PARTITION 实例，如下所示。我们有三个大小为 W、W/2-x1 和 x1 的容器。最初，第一个容器包含大小为 x1、x2、...、xn[=43= 的项目] 而另外两个是空的。要插入的新项目的大小为 W/2。我们观察到当且仅当原始 PARTITION 问题有解时，这个新项目才能插入到这些容器中。
编辑添加（更多证明细节）
首先，我们假设我们有原始分区问题的解决方案，即：将 x 分成两个子集 S1 和 S2 这样每个子集中的 x 的总和等于 W/2。假设 S1 包含最小元素 x1。然后，我们可以将 x1 移动到第三个容器中，并将 S1 的所有其他元素移动到第二个容器中，从而留下 space 的 W/2 在新项目的第一个容器中。
接下来，假设我们有某种方法可以将新的 W/2 大小的元素插入到这些容器中。通过检查，发生这种情况的唯一方法是在第一个容器中为其创建 space ； 可能发生的唯一方法是将正好 W/2 的物品移出（并因此留下正好 W/2 的物品）第一个容器。显然，这定义了将原始项目集拆分为两个子集，使得每个子集的大小为 W/2.
现在，仅仅因为这个问题是 NP 完全的并不意味着一切都丢失了。它只是意味着，如果您认为您已经想出了一个可以在多项式时间内解决所有实例的解决方案，那么您应该检查一下您的工作。您将看到的实例类型的结构（例如："low amount of large containers and huge amount of items in them"）可能有助于指导搜索有用的启发式方法。