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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Проблема с почтовой маркой»  – Новости  · газеты  · книги  · ученый  · JSTOR (Июнь 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

Сложность

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

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

• Проблема с монетой
• Задача о рюкзаке
• Проблема суммы подмножества

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

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

• Ланнон, У. Ф. (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 марки)