Уменьшить сумму подмножества до Полимино Упаковка

Question

Это домашнее задание, поэтому любая помощь оценивается.

Я должен доказать, что следующая проблема NP-полная. В подсказке говорится, что вы должны уменьшить проблему суммирования подмножества к этой проблеме.

Учитывая множество форм, как ниже, и мп матрицы с размерностью доска, решить, можно ли покрыть доску полностью со всеми формами. Обратите внимание, что фигуры не могут вращаться.

Например, для платы 3 × 5 и следующих частей, плата может быть покрыта так:

Теперь важно отметить, заключается в том, что задачу суммирования подмножества, которую мы пытаемся уменьшить, следует указывать в виде многочлена длины ввода в терминах m и n.

Любые идеи для использования другой NP-полной проблемы оценены.

Answer 1

Я бы рекомендовал сделать это сокращение в два этапа.

Сначала уменьшите сумму подмножества до partition problem. Эта проблема связана с подмножеством, за исключением того, что вместо того, чтобы быть заданной целью k, цель состоит в том, чтобы разбить множество на две точно равные половины. Это не слишком сложно (я оставлю это как упражнение), и сделать следующую часть намного проще.

Далее, уменьшите проблему раздела до проблемы с черепицей. Интуитивно идея заключается в следующем. Если входные числа в задаче разбиения являются п , п , ..., N _K, создавать плитки, размеры которых 3n × 1, 3n × 1, ... , и 3n _k × 1, где w - некоторое число, которое мы выберем позже. Затем, если сумма чисел во входном наборе равна 2N (это означает, что целью является разделение набора на два подмножества, суммирующие до N каждый), создайте плату 3N × 2.

Интуиция заключается в том, что если мы сможем разбить набор на два подмножества с равной суммой, то мы сможем выложить эту доску, взяв все цифры из первой половины, выбирая эти плитки, а затем укладывая их из конца в конец образуют прямоугольник 3N × 1. Затем мы можем взять числа из оставшейся половины и использовать их для формирования прямоугольника 3N × 1, поэтому ставим первую строку плитки в верхнем ряду, а вторая строка плиток во второй строке полностью разбивает плату.

Чтобы показать, что в другом направлении работает, сначала обратите внимание, что плитки имеют размер не менее 3 × 1, поэтому они должны быть ориентированы слева направо. Поэтому, если мы можем плитку доски, мы нашли способ разделить плитки на две группы, ширина которых равна, поэтому есть способ разбить набор на две части с равной суммой.

В целом размер входных данных растет не более чем на многочлен (мы умножаем размер каждого номера, который добавляет не более двух бит к каждой длине входного номера), а размер платы полиномиально больше как вход. Поэтому, в целом, сокращение требует только полиномиального времени для оценки.

Надеюсь, это поможет!