algorithm - Google APAC(CodeJam) 平铺算法

Question

我被困在以下问题 Problem Statement .我已经考虑了一段时间，然后查看了问题的一些线索，因为我想不出解决方案。我的理解是，这是“Bin Packing”问题的特例，通常是 NP-Hard。特别看这个想法CodeForces Blog Idea ，我无法理解为什么这甚至在这里效果最佳。特别是我们如何证明这个算法是最优的？

Problem Statement :

Enzo is doing renovation for his new house. The most difficult part is to buy exactly the right number of tiles. He wants N tiles of different sizes. Of course they have to be cut from the tiles he bought. All the required tiles are square. The lengths of side of the tiles are 2^S1, 2^S2, ..., 2^SN. He can only buy a lot of tiles sized M*M, and he decides to only cut tiles parallel to their sides for convenience. How many tiles does he need to buy?

Answer 1

所提出的解决方案的本质是首次拟合递减 (FFD) 启发式。

如果对于每个 a_i < a_j，我们将 Bin Packing 问题的大小称为嵌套， a_i = k_ij a_j。注意，根据这个定义，原始问题是嵌套装箱问题。

让我们证明 FFD 启发式解决了 Nesting Bin Packing。考虑一个反例:项目大小的非递增序列 a_i 和 FFD 启发式算法无法实现的最优解 OPT。第一个 i 需要 bin 编号 OPT+1。这意味着，之前的所有项目都已打包，没有空间容纳项目 i。

让我们比较一下使用 FFD 的前 i-1 个项目的分布和 i 个项目的最优分布。最佳分布中放置的项目的总大小高 a_i。因此，对于至少一个 bin，最优分布中的项目总大小大于 FFD 分布中的项目总大小。由于嵌套，到目前为止考虑的所有项目可能会分成一定数量的 a_i 大小的项目，因此两个总数都是a_i，它们之间的最小可能差异是 a_i。因此，我们为项目 i 找到了一个 bin，这导致了矛盾。

矛盾在 1D 情况下很明显(原始 Bin Packing 问题)，但在 2D 情况下就不那么明显了。让我们引入一个单元格大小为 A=√a_i 且原点位于左上角的网格。已放置标题的边长将是 A 的倍数。我们会将两个解决方案中的所有标题移到顶部(按从上到下的顺序)，然​​后移到左侧(按从左到右的顺序)。之后，所有图 block 在网格上都将具有整数坐标。但是最优解中被占用的单元比FFD中的要多，所以应该至少有一个A×A单元在最优解中被占用，而FFD中是空闲的。让我们用它来放置方 block i。