Проблема: нам дают набор палочек, имеющих целую длину. Общая сумма их длин n (n + 1) / 2.
Можем ли мы разбить их, чтобы получить палочки размером за полиномиальное время?
Удивительно, но единственная ссылка, которую я нахожу для этой проблемы, - это древнее обсуждение:
http://www.iwriteiam.nl/cutsticks.html
Что еще известно о проблеме? Можем ли мы доказать, что проблема «в подвешенном состоянии»?
Обновление: проблема с режущими палками имеет ограничение, что каждая палка имеет длину не менее единиц. (См. Комментарии и ответ Цуёси для случая без ограничений).
Ответы:
Предостережение: как Юкка Суомела прокомментировал вопрос, на странице, связанной с вопросом, находится проблема, отличная от проблемы, указанной в вопросе, в том, что проблема на странице имеет ограничение, состоящее в том, что длина данных палочек больше или равна п. Этот ответ о проблеме без этого ограничения. Поскольку комментарий Эмиля по этому вопросу относится к проблеме с ограничением, нет противоречия между его комментарием и следующим ответом.
Проблема является NP-полной, даже если числа даны в одинарных.
3-секционная задача - это следующая проблема:
Экземпляр : положительные целые числа a 1 ,…, a n в унарном, где n = 3m, а сумма n целых чисел равна mB, так что каждое a i удовлетворяет B / 4 < а я <B / 2.
Вопрос : Можно ли разбить целые числа a 1 ,…, a n на m мультимножеств, чтобы сумма каждого мультимножества была равна B?
Задача с 3 разделами является NP-полной, даже если a 1 ,…, a n все различны [HWW08] (спасибо Сержу Гасперсу за то, что он рассказал мне об этом ). Можно ограничить эту ограниченную версию задачи с 3 разделами следующим образом.
Предположим, что нам дан пример задачи с 3 разбиениями, состоящей из различных положительных целых чисел a 1 ,…, a n . Пусть m = n / 3 и B = (a 1 +… + a n ) / m, и пусть N будет максимумом среди a i . Рассмотрим следующий случай с проблемой палки: экземпляр состоит из одной палки длины k для каждого k∈ {1,…, N} ∖ {a 1 ,…, a n } и m палок длины B. Используя факт что каждый a i удовлетворяет a i > B / 4 ≥ N / 2, нетрудно доказать, что эта проблема со стержнем имеет решение тогда и только тогда, когда решение задачи с 3 разбиениями имеет решение.
Ссылки
[HWW08] Хизер Хьюлетт, Тодд Дж. Уилл, Герхард Дж. Вёджингер. Мультиграф реализации последовательностей степеней: максимизация проста, минимизация трудна. Письма об исследовании операций , 36 (5): 594–596, сентябрь 2008 г. http://dx.doi.org/10.1016/j.orl.2008.05.004
источник