3

我需要设计一种算法来进行简单的碎片整理，但具有“最小更改量”功能。假设我有 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

我已经做了一些研究，我只能找到背包问题或好友算法，但我不确定这些是否真的是我想要的。

你们中的任何人都可以帮助我尽可能简单地设计这个算法吗？我正在解决一种情况，即我将有少量的大型容器和大量的物品，因此列举所有可能性并不是最优的。

非常感谢！

更新只是为了弄清楚我在问什么-确定是否可以通过仅进行一项更改来解决这种情况是没有问题的。问题是，当“单步走”不可能时，如何找到最少的替换数量。

4

2 回答 2

1

这不是问题的答案，但评论太长了。此处所述的问题是 NP 完全问题（一旦我们将其适当地更改为决策问题），可以从PARTITION 问题中简化。

令 x 1 , x 2 , ..., x n是 PARTITION 问题的一个实例。为了便于表示，让我们取 x 1为 x 中最小的 x 的大小，让 W 为所有 x 的总和。此外，为简单起见，让我们假设 W 是偶数。

我们构造给定问题的一个实例来对我们的 PARTITION 实例进行如下编码。我们有三个大小为 W、W/2-x 1和 x 1的容器。最初，第一个容器包含大小为 x 1、 x 2、...、x n的项目，另外两个是空的。要插入的新项目的大小为 W/2。我们观察到，当且仅当原始 PARTITION 问题有解决方案时，才能将这个新项目插入这些容器中。

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

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

接下来，假设我们有某种方法可以将新的 W/2 大小的元素插入到这些容器中。通过检查，发生这种情况的唯一方法是在第一个容器中为它腾出空间；唯一可能发生的方法是将价值 W/2 的物品准确地移出（因此，准确地留下价值 W/2 的物品）第一个容器。显然，这定义了将原始项目集拆分为两个子集，使得每个子集的大小为 W/2。

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

于 2015-12-08T01:24:10.190 回答
0

如果这些容器是从头开始构建的，您可以添加状态以说明哪个容器填充最少，并始终将下一个项目放在那里。

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

只是我的2美分。

于 2015-12-07T20:11:28.810 回答