进行最小程度的碎片整理

马雷克·加林斯基(Marek Galinski)

我需要设计一种执行简单碎片整理的算法,但要具有“最少更改”功能。假设我有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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

使用TSHARK进行碎片整理

内核是否进行了碎片整理

对XFS进行碎片整理的命令是什么?

Btrfs是否需要进行碎片整理?

不能进行碎片整理的占位符视图

为什么对SSD进行碎片整理很不好?

在预蜂窝上进行碎片整理/减少堆大小

UNIX何时进行“碎片整理”?(特别是Solaris)

如何在PostgreSQL中找出碎片索引并对其进行碎片整理?

碎片整理术语说明

从Linux整理NTFS分区的碎片

整理内存碎片/ OOM故障

对USB闪存驱动器进行碎片整理很不好吗?

电源听起来像是对硬盘进行了碎片整理

Firebird会进行碎片整理吗?如果可以的话,像聚集索引吗?

是否应该在Windows 10(NT)上对HDD进行碎片整理?

无法对硬盘进行碎片整理,CSC1.tmp中的错误

是否有用于对NTFS分区进行碎片整理的Linux工具?

btrfs —对具有只读快照的子卷进行碎片整理有危险吗?

如何对部分填充的sqlite页面进行碎片整理/合并以回收空间?

对NTFS分区进行碎片整理而不会弄乱ext4分区

如何对ext4文件系统进行碎片整理

我应该多久对驱动器进行一次碎片整理?

如何对几乎没有可用空间的大型TrueCrypt卷进行碎片整理

有谁知道无法对 Outlook .ost 文件进行碎片整理是否“正常”?

整理硬盘碎片时,“多余碎片”是什么?

在Ubuntu 16.04上是否需要进行碎片整理?除BleachBit之外,我还需要其他维护吗?

如何仅在ext4文件系统中对大小小于100MB的文件进行碎片整理

如果告诉您,Windows 7是否可以对SSD驱动器进行实际的碎片整理?

TOP 榜单

热门标签

归档