Frimärksproblem

Frimärksproblemet är en matematisk gåta som frågar vad som är det minsta portovärdet som inte kan placeras på ett kuvert, om det senare bara kan innehålla ett begränsat antal frimärken, och dessa får bara ha vissa specificerade nominella värden .

Anta till exempel att kuvertet bara kan innehålla tre frimärken och att de tillgängliga frimärksvärdena är 1 cent, 2 cent, 5 cent och 20 cent. Då är lösningen 13 cent; eftersom ett mindre värde kan erhållas med högst tre stämplar (t.ex. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), men för att få 13 cent måste man använda minst fyra stämplar.

Matematisk definition

Matematiskt kan problemet formuleras på följande sätt:

Givet ett heltal m och en mängd V med positiva heltal, hitta det minsta heltal z som inte kan skrivas som summan v ₁ + v ₂ + ··· + v _k av något antal k ≤ m av (inte nödvändigtvis distinkta) element av V .

Komplexitet

Detta problem kan lösas genom brute force search eller backtracking med maximal tid proportionell mot | V | ^m , där | V | är antalet distinkta stämpelvärden tillåtna. Därför, om kapaciteten för enveloppen m är fixerad, är det ett polynomtidsproblem . Om kapaciteten m är godtycklig är problemet känt för att vara NP-hårt .

Se även

externa länkar

Lunnon, WF (1969). "Ett frimärksproblem" . Comput. J . 12 (4): 377–380. doi : 10.1093/comjnl/12.4.377 .
Alter, R.; Barnett, JA (1980). "Ett frimärksproblem". Amer. Matematik. Månadsvis . 87 (3): 206–210. doi : 10.2307/2321610 . JSTOR 2321610 .
Graham, RL; Sloane, NJA (1980). "På additiva baser och harmoniska grafer". SIAM J. Algebr. Diskreta metoder . 1 (4): 382–404. CiteSeerX 10.1.1.70.5521 . doi : 10.1137/0601045 .
Challis, MF (1993). "Två nya tekniker för beräkning av extrema h -baser A _k " . Comput. J . 36 (2): 117–126. doi : 10.1093/comjnl/36.2.117 .
Kohonen, J.; Corander, J. (2013). "Additionskedjor möter frimärken: minska antalet multiplikationer". arXiv : 1310.7090 [ math.NT ].
Kohonen, Jukka (2014). "En meet-in-the-middle-algoritm för att hitta extremt begränsade additiv 2-baser". arXiv : 1403.5945 [ math.NT ].
Weisstein, Eric W. "Portostämpelproblem" . MathWorld .
OEIS- sekvens A001212 (Lösning på frimärksproblemet med n valörer och 2 frimärken)