Google APAC (CodeJam) Алгоритм черепицы

Question

Я застрял в следующем вопросе Problem Statement. Я подумал об этом некоторое время, а затем посмотрел на некоторые подсказки для проблемы, потому что я не мог придумать решение. Я понимаю, что это особый случай проблем с «Bin Packing», которые в целом являются NP-Hard. Глядя на эту идею, в частности CodeForces Blog Idea, я не могу понять, почему это даже работает оптимально здесь. В частности, как мы можем доказать, что этот алгоритм оптимален?

Постановка задачи:

Энцо делает ремонт в своем новом доме. Самая сложная часть - , чтобы купить точное количество плиток. Он хочет N плиток разных размеров. Разумеется, их нужно вырезать из плиток, которые он купил у . Все необходимые плитки квадратные. Длина сторон плитки равна 2^S1, 2^S2, ..., 2^SN. Он может купить только много плиток размером M * M, и он решает только разрезать плитки параллельно их бокам для удобства . Сколько плиток нужно купить?

Answer 1

Суть предлагаемого решения является первым нужным уменьшением (FFD) эвристики.

размеры вызова Давайте из за Bin упаковки проблемы вложенности если для каждого _я < _J, _я = к _{IJ J}. Обратите внимание, что в соответствии с этим определением исходной проблемой является Упаковка гнездящей упаковки проблема.

Давайте доказательство того, что эвристика FFD решает Упаковка вложенного бина. Рассмотрим встречный пример: невозрастающая последовательность размеров позиций a _i и оптимальное решение OPT, которое не достигается эвристикой FFD. Существует первый i, который требует номер ячейки OPT + 1. Это означает, что все предыдущие элементы были упакованы, и нет места для позиции i.

Давайте сравним распределение первого я-1 элементы с использованием FFD и оптимальное распределение я пунктов. Общий размер размещенных предметов в оптимальном распределении выше на a _i. Таким образом, по крайней мере для одного бина общий размер элементов в оптимальном распределении больше, чем в распределении FFD. Благодаря вложенности все элементы, рассмотренные до сих пор, может быть разделен на некоторое количество а _I -sized пунктов, так как итоговые суммы кратные _я, а минимальная возможная разница между ними в _i. Поэтому мы нашли корзину для предмета i, что приводит к противоречию.

Противоречие ясно в 1D корпусе (оригинал Bin Packing проблема), но не так ясно для 2D-футляра. Введем сетку с размером ячейки A = √a _i и происхождение в верхнем левом углу. Длина стороны уже размещенного названия будет кратной A. Мы переместим все заголовки в обоих решениях вверх (по порядку сверху вниз), затем влево (в порядке слева направо). После этого все плитки будут иметь целые координаты на сетке. Но в оптимальном решении есть более занятые ячейки, чем FFD, поэтому должна быть хотя бы одна ячейка A × A, которая занята в оптимальном решении и свободна в FFD. Давайте использовать его для размещения плитки i.