Проблема с почтовой маркой - Postage stamp problem

В проблема с почтовой маркой это математический Загадка, которая спрашивает, какова наименьшая стоимость почтовой оплаты, которую нельзя поместить на конверт, если последний может содержать только ограниченное количество марок, и они могут иметь только определенные указанные номиналы.[1]

Например, предположим, что конверт может содержать только три марки, а доступные марки - 1 цент, 2 цента, 5 центов и 20 центов. Тогда решение 13 центов; поскольку любое меньшее значение может быть получено не более чем с тремя марками (например, 4 = 2 + 2, 8 = 5 + 2 + 1 и т. д.), но чтобы получить 13 центов, нужно использовать как минимум четыре марки.

Математическое определение

Математически задачу можно сформулировать следующим образом:

Учитывая целое число м и набор V положительных целых чисел, найдите наименьшее целое число z это не может быть записано как сумма v1 + v2 + ··· + vk некоторого числа k ≤ м из (не обязательно отдельных) элементов V.

Сложность

Эту проблему можно решить с помощью поиск грубой силы или же возврат с максимальным временем, пропорциональным |V |м, где |V | - допустимое количество различных значений штампа. Следовательно, если емкость конверта м фиксируется, это полиномиальное время проблема. Если емкость м произвольно, проблема, как известно, NP-жесткий.[1]

Смотрите также

Рекомендации

  1. ^ а б Джеффри Шаллит (2001), Вычислительная сложность задачи местной почтовой марки. SIGACT News 33 (1) (март 2002 г.), 90-94. Доступно 30 декабря 2009 г.

внешняя ссылка

  • Ланнон, У. Ф. (1969). «Проблема с почтовой маркой». Comput. J. 12 (4): 377–380. Дои:10.1093 / comjnl / 12.4.377.
  • Alter, R .; Барнетт, Дж. А. (1980). «Проблема с почтовой маркой». Амер. Математика. Ежемесячно. 87 (3): 206–210. Дои:10.2307/2321610. JSTOR  2321610.
  • Graham, R.L .; Слоан, Н. Дж. А. (1980). «Об аддитивных основах и гармоничных графах». SIAM J. Algebr. Дискретные методы. 1 (4): 382–404. CiteSeerX  10.1.1.70.5521. Дои:10.1137/0601045.
  • Чаллис, М. Ф. (1993). «Два новых метода вычисления экстремальных час-базы Аk". Comput. J. 36 (2): 117–126. Дои:10.1093 / comjnl / 36.2.117.
  • Kohonen, J .; Корандер, Дж. (2013). «Сложение цепочек соответствует почтовым маркам: уменьшение количества умножений». arXiv:1310.7090 [math.NT ].
  • Кохонен, Юкка (2014). «Алгоритм встречи посередине для поиска экстремальных ограниченных аддитивных 2-базисов». arXiv:1403.5945 [math.NT ].
  • Вайсштейн, Эрик В. "Проблема с почтовой маркой". MathWorld.
  • OEIS последовательность A001212 (Решение проблемы почтовых марок с п купюры и 2 марки)