Problém s poštovní známkou - Postage stamp problem

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Problém s poštovní známkou“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Červen 2017) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The problém s poštovní známkou je matematický hádanka, která se ptá, co je nejmenší hodnota poštovného, ​​kterou nelze vložit na obálku, pokud ta může obsahovat pouze omezený počet známek, které mohou mít pouze určité zadané nominální hodnoty.^[1]

Předpokládejme například, že obálka může obsahovat pouze tři známky a dostupné hodnoty razítka jsou 1 cent, 2 centy, 5 centů a 20 centů. Pak je řešení 13 centů; jakoukoli menší hodnotu lze získat maximálně třemi známkami (např. 4 = 2 + 2, 8 = 5 + 2 + 1 atd.), ale pro získání 13 centů musíte použít alespoň čtyři známky.

Matematická definice

Matematicky lze problém formulovat následovně:

Dáno celé číslo m a sada PROTI kladných celých čísel, najděte nejmenší celé číslo z to nelze zapsat jako součet proti₁ + proti₂ + ··· + proti_k nějakého čísla k ≤ m (ne nutně odlišných) prvků PROTI.

Složitost

Tento problém lze vyřešit pomocí hledání hrubou silou nebo ustoupit s maximálním časem úměrným |PROTI |^m, kde |PROTI | je počet povolených odlišných hodnot razítka. Proto, pokud je kapacita obálky m je pevná, je to polynomiální čas problém. Pokud kapacita m je libovolný, je známo, že problém je NP-tvrdé.^[1]

Viz také

• Problém s mincemi
• Problém s batohem
• Problém se součtem podmnožiny

Reference

externí odkazy

• Lunnon, W. F. (1969). "Problém s poštovní známkou". Comput. J. 12 (4): 377–380. doi:10.1093 / comjnl / 12.4.377.
• Alter, R .; Barnett, J. A. (1980). "Problém s poštovní známkou". Amer. Matematika. Měsíční. 87 (3): 206–210. doi:10.2307/2321610. JSTOR  2321610.
• Graham, R.L .; Sloane, N. J. A. (1980). "Na aditivních základech a harmonických grafech". SIAM J. Algebr. Diskrétní metody. 1 (4): 382–404. CiteSeerX  10.1.1.70.5521. doi:10.1137/0601045.
• Challis, M. F. (1993). „Dvě nové techniky pro výpočet extremálního h-základny A_k". Comput. J. 36 (2): 117–126. doi:10.1093 / comjnl / 36.2.117.
• Kohonen, J .; Corander, J. (2013). "Sčítací řetězce splňují poštovní známky: snížení počtu rozmnožování". arXiv:1310.7090 [math.NT ].
• Kohonen, Jukka (2014). "Algoritmus pro setkávání ve středu pro hledání extrémně omezených aditivních 2 bází". arXiv:1403.5945 [math.NT ].
• Weisstein, Eric W. „Problém s poštovní známkou“. MathWorld.
• OEIS posloupnost A001212 (Řešení problému s poštovní známkou s n nominální hodnoty a 2 známky)