Проблема с почтовой маркой

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

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

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

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

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

Сложность

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

См. также

Ссылки

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

Внешние ссылки

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

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

[1]