切手の問題

切手問題は、封筒に貼れる切手の枚数が限られており、切手の額面も特定のものに限られている場合、封筒に貼ることができない最小の切手金額はいくらか、という数学的な謎かけである。 ^{[ 1 ]}

例えば、封筒に切手が3枚しか入らないとして、使える切手の額面が1セント、2セント、5セント、20セントだとします。この場合、正解は13セントです。なぜなら、それより小さい金額は最大3枚の切手で表現できますが（例えば、4セントは2セント＋2セント、8セントは5セント＋2セント＋1セントなど）、13セントにするには少なくとも4枚の切手が必要だからです。

数学的に言えば、この問題は次のように定式化できる。

整数mと正の整数の集合Vが与えられたとき、 Vの (必ずしも異なるとは限らない) 要素のk ≤ mの数の和v ₁ + v ₂ + ··· + v _kとして表せない最小の整数z を見つけます。

この問題は、総当たり探索またはバックトラッキングによって解決でき、最大時間は | V | ^mに比例します。ここで、| V | は許可される異なる切手の値の数です。したがって、封筒の容量mが固定されている場合は、多項式時間の問題となります。容量mが任意の場合、この問題はNP 困難であることが知られています。^{[ 1 ]}

• コインの問題
• ナップサック問題
• 部分和問題

• Lunnon, WF (1969). "切手問題" . Comput. J. 12 ( 4): 377–380 . doi : 10.1093/comjnl/12.4.377 .
• Alter, R.; Barnett, JA (1980). "切手の問題". Amer. Math. Monthly . 87 (3): 206–210 . doi : 10.2307/2321610 . JSTOR 2321610 . 
• Graham, RL ; Sloane, NJA (1980). "加法基底と調和グラフについて". SIAM J. Algebr. Discrete Methods . 1 (4): 382– 404. CiteSeerX 10.1.1.70.5521 . doi : 10.1137/0601045 . 
• Challis, MF (1993). "極値h基底A _kを計算するための2つの新しい手法" . Comput. J . 36 (2): 117– 126. doi : 10.1093/comjnl/36.2.117 .
• Kohonen, J.; Corander, J. (2013). "加算連鎖と切手：乗算回数の削減". arXiv : 1310.7090 [ math.NT ].
• Kohonen, Jukka (2014). "極値制限加法2基底を見つけるための中間一致アルゴリズム". arXiv : 1403.5945 [ math.NT ].
• ワイスタイン、エリック W. 「切手問題」。マスワールド。
• OEISシーケンスA001212 （ n種類の額面と2種類の切手を用いた切手問題の解法）