algorithm - Google APAC(CodeJam) 平铺算法

我被困在以下问题 Problem Statement 。我已经考虑了一段时间，然后查看了问题的一些线索，因为我无法想出解决方案。我的理解是，这是“装箱”问题的特例，通常是 NP-Hard。看着这个想法，特别是 CodeForces Blog Idea ，我无法理解为什么这在这里甚至可以最佳地工作。特别是我们如何证明这个算法是最优的？ 最佳答案 所提出的解决方案的本质是首次拟合递减(FFD)启发式。如果对于每个 ai 让我们证明 FFD 启发式算法可以解决 Nesting Bin Packing。考虑一个反例:项目大小 ai 的非递增序列和 FFD 启发式无法实现的最佳解决方案 OPT。第一个 i 需要 bin 编号 OPT+1。这意味着，之前的所有项目都已打包，项目 i 没有空间。让我们比较使用 FFD 的前 i-1 个项目的分布和 i 个项目的最优分布。最佳分布中放置的物品的总大小比ai高。因此，对于至少一个 bin，最优分布的项目总大小大于 FFD 分布。由于嵌套，到目前为止考虑的所有项目可能会被拆分为一定数量的 ai 大小的项目，因此两个总数都是 ai 的倍数，并且它们之间可能的最小差异是 ai。因此，我们为项目 i 找到了一个 bin，这导致了矛盾。矛盾在一维情况下很明显(原始装箱问题)，但在二维情况下就不那么明显了。让我们引入一个单元格大小为 A=√ai 且原点在左上角的网格。已放置标题的边长将是 A 的倍数。我们将两个解决方案中的所有标题移到顶部(从上到下的顺序)，然​​后向左(从左到右的顺序)。之后，所有瓷砖将在网格上具有整数坐标。但是最优解中被占用的单元比FFD的要多，所以在最优解中应该至少有一个A×A的单元被占用，而在FFD中是空闲的。让我们用它来放置瓷砖 i。关于algorithm - Google APAC(CodeJam) 平铺算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40266313/