切手問題

切手問題とは、ある枚数の切手で作れない最小の金額（郵便料金）を求める数学の問題であるJeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94.  Accessed on 2009-12-30.。封筒の面積の制約上、貼れる切手の枚数が限られているとする。このとき、数種類の額面の切手を組み合わせて構成できない最小の郵便料金を問うものである。 

例えば、封筒には3枚の切手しか貼れないとする。使用可能な切手の額面が1円、2円、5円、20円の場合、12円までの金額は3枚までの切手で構成できる（例えば、4=2+2、8=5+2+1、11=5+5+1）。しかし、13円を構成するには少なくとも4枚の切手が必要となるため、13が解となる。 

 数学的な定義 
数学的には、問題は次のように定式化される。 

 整数 m と正の整数の集合 V が与えられたとき、k ≤ m なる k 個の要素の和 v1 + v2 + ··· + vk で表せない最小の整数 z を求めよ。 

 特殊な場合 
 n 種類、2枚の切手での解 
n種類を適切に選ぶと、2枚の切手での解は最大で
2, 4, 8, 12, 16, 20, 26, 32, 40, 46, 54, 64, 72, 80, 92, 104, 116, 128, 140, 152, 164, 180, 196, 212,... ()
となる。

例えば、順に

となる。

 2 種類、h 枚の切手での解 
2 種類を適切に選ぶと、h枚の切手での解は最大で
2, 4, 7, 10, 14, 18, 23, 28, 34, 40, 47, 54, 62, 70, 79, 88, 98, 108, 119, 130, 142, 154, 167, 180,... ()
となる。

例えば、順に

となり、一般にの切手を用意することで最大化でき、その解は

と表せる。

 3 種類、h 枚の切手での解 
3種類を適切に選ぶと、 h 枚の切手での解は最大で
3, 8, 15, 26, 35, 52, 69, 89, 112, 146, 172, 212, 259, 302, 354, 418, 476, 548, 633, 714, 805, 902, 1012, 1127, 1254, 1382,... ()
となる。

n ≥ 20 のとき

とおくと

が  h 枚の切手での最大の解を与え、その最大の解は

ここで A, B は

となる
。

 計算複雑性 
この問題は、 総当たりまたはバックトラッキングで |V|m の定数倍時間で解くことができる。ここで |V| は使用できる切手の額面の種類の数とする。したがって、封筒の容量 m が定数である場合、多項式時間で解ける問題である。容量 m が任意の場合、問題はNP困難である。 

 関連項目 

 フロベニウスの硬貨交換問題 切手の枚数に制限がない場合に相当
 ナップサック問題 
 部分和問題 

 参考文献 

 外部リンク 






Category:数学の問題
Category:応用数学
Category:数学パズル
Category:加法的整数論
Category:数学に関する記事