我需要设计一种执行简单碎片整理的算法，但要具有“最少更改”功能。假设我有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算法，但是我不确定这些是否真的是我想要的。
你们中的任何人都可以帮助我设计尽可能简单的算法吗？我正在解决一种情况，即我的大型容器数量很少，而其中的物品数量却很多，因此枚举所有可能性并不是最佳选择。
非常感谢！
更新只是为了弄清楚我在问什么-只需更改一项即可确定情况是否可以解决。问题是，当不可能“单步移动”时，如何找到最小的更换数量。
这不是问题的答案，但是评论太久了。此处所述的问题是NP完全的（一旦我们适当地将其更改为决策问题），可以从PARTITION问题还原。
令x 1，x 2，...，x n是PARTITION问题的一个实例。为了说明起见，让我们将x 1设为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完全的，并不意味着所有的一切都丢失了。这只是意味着，如果您认为自己想出了一种可以在多项式时间内解决所有实例的解决方案，那么您应该检查一下工作。您将看到的实例类型的结构（例如：“少量的大型容器，其中没有大量的物品”）可能有助于指导搜索有用的启发式方法。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句