Problem ze znaczkiem pocztowym

Problem znaczka pocztowego to zagadka matematyczna , która pyta, jaka jest najmniejsza wartość pocztowa, której nie można umieścić na kopercie, jeśli ta ostatnia może pomieścić tylko ograniczoną liczbę znaczków, a te mogą mieć tylko określone nominały.

Załóżmy na przykład, że w kopercie mieszczą się tylko trzy znaczki, a dostępne wartości znaczków to 1 cent, 2 centy, 5 centów i 20 centów. Wtedy rozwiązaniem jest 13 centów; bo każdą mniejszą wartość można uzyskać najwyżej trzema znaczkami (np. 4 = 2 + 2, 8 = 5 + 2 + 1 itd.), ale aby otrzymać 13 centów, trzeba użyć co najmniej czterech znaczków.

Definicja matematyczna

Matematycznie problem można sformułować następująco:

Mając daną liczbę całkowitą m i zbiór V dodatnich liczb całkowitych, znajdź najmniejszą liczbę całkowitą z , której nie można zapisać jako sumę v ₁ + v ₂ + ··· + v _k pewnej liczby k ≤ m (niekoniecznie odrębnych) elementów V. _

Złożoność

Problem ten można rozwiązać poprzez wyszukiwanie metodą brute-force lub cofanie się z maksymalnym czasem proporcjonalnym do | V | ^m , gdzie | V | to liczba dozwolonych różnych wartości stempla. Dlatego też, jeśli pojemność obwiedni m jest stała, jest to problem czasu wielomianowego . Jeśli pojemność m jest dowolna, wiadomo, że problem jest NP-trudny .

Zobacz też

Linki zewnętrzne

Lunnon, WF (1969). „Problem ze znaczkiem pocztowym” . Oblicz. J. _ 12 (4): 377–380. doi : 10.1093/comjnl/12.4.377 .
Alter, R.; Barnett, JA (1980). „Problem ze znaczkiem pocztowym”. Amera. Matematyka. Miesięcznie . 87 (3): 206–210. doi : 10.2307/2321610 . JSTOR 2321610 .
Graham, Republika Południowej Afryki; Sloane, NJA (1980). „O bazach addytywnych i harmonijnych wykresach”. SIAM J. Algebr. Metody dyskretne . 1 (4): 382–404. CiteSeerX 10.1.1.70.5521 . doi : 10.1137/0601045 .
Challis, MF (1993). „Dwie nowe techniki obliczania ekstremalnych baz h A _k ” . Oblicz. J. _ 36 (2): 117–126. doi : 10.1093/comjnl/36.2.117 .
Kohonen, J.; Corander, J. (2013). „Łańcuchy dodawania spotykają się ze znaczkami pocztowymi: zmniejszenie liczby mnożeń”. arXiv : 1310,7090 [ matematyka.NT ].
Kohonen, Jukka (2014). „Algorytm spotkania w środku do znajdowania ekstremalnie ograniczonych addytywnych 2 zasad”. arXiv : 1403,5945 [ matematyka.NT ].
Weisstein, Eric W. „Problem ze znaczkiem pocztowym” . Świat Matematyki .
OEIS A001212 (Rozwiązanie problemu znaczków pocztowych z n nominałami i 2 znaczkami)