谷歌亚太区(CodeJam)平铺算法

Question

谷歌亚太区(CodeJam)平铺算法

3

我卡在了这个问题上问题陈述。我思考了一段时间，然后查看了一些线索，因为我无法想出解决方案。我的理解是，这是“装箱”问题的特殊情况，通常是NP难题。具体来看CodeForces Blog Idea，我无法理解为什么这里甚至能够最优地工作。特别是我们如何证明此算法是最优的？

问题陈述：

Enzo正在为他的新房子进行装修。最困难的部分是准确购买所需数量的瓷砖。他想要不同尺寸的N块瓷砖。当然，他们必须从他买的瓷砖中切割。所有所需的瓷砖都是正方形的。这些瓷砖边长为2^S1、2^S2、…、2^SN。他只能购买大小为M*M的瓷砖批次，并且为方便起见，他决定只沿着它们的边切割瓷砖。他需要购买多少块瓷砖？

- random40154443

或者另一个解决这个问题的算法，只要有令人信服的正确性证明也可以。 - random40154443

3

这不是证明，而是一些概念性的直觉：贪心算法在装箱问题上通常不是最优解的原因是两个较小的正方形可以比一个大正方形更大。由于此问题中所有边长都是2的幂次方，所以这种情况不会发生。 - Vincent van der Weele

我理解这里的问题在于箱子可以相互嵌套，但正式地说，我不明白这如何有所帮助。 - random40154443

2

我认为证明可以如下进行：给定任意解，你能证明你可以对齐所有正方形，使得每个切割都是断头台式的切割（即从矩形的一侧直接切到另一侧）吗？这应该是可能的，因为有2的幂次方。然后你需要证明的是按降序处理正方形是最优的。这可以通过证明如果较小的正方形在较大的正方形之后不适合，它们两个都不会适合来证明。 - Vincent van der Weele

请问您能否详细说明一下2的幂如何在证明第一个子部分中发挥作用？ - random40154443

显示剩余6条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kgeorgiy · Accepted Answer

所提出的解决方案的实质是“首次递减”（FFD）启发式算法。

如果对于每个a_i < a_j，a_i = k_ij a_j，则称装箱问题的尺寸为“嵌套”。注意，根据这个定义，原始问题是“嵌套装箱”问题。

让我们证明FFD启发式算法解决了“嵌套装箱”问题。考虑一个反例：非递增的物品尺寸序列和一个不是通过FFD启发式算法实现的最优解OPT。存在第一个 i 需要容器号OPT+1。这意味着所有先前的项目都已打包，并且没有空间放置项目 i 。

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

在一维情况下（原始“装箱”问题），这个矛盾很明显，但对于二维情况来说并不那么清楚。让我们引入一个单元格大小为A=√a_i的网格，并将原点放在左上角。已放置标题的边长将是A的倍数。我们将两种解决方案中的所有标题向上移动（从上到下顺序），然后向左移动（从左到右顺序）。之后，所有标题将在网格上具有整数坐标。但是，在最优解中占用的单元格比FFD多，因此最优解中应该至少有一个A×A的单元格在最优解中被占用，在FFD中是空闲的。让我们使用它来放置标题 i 。