切手問題

切手問題とは、ある枚数の切手で作れない最小の金額（郵便料金）を求める数学の問題である。封筒の面積の制約上、貼ることのできる切手の枚数が限られているとする。このとき、数種類の額面の切手を組み合わせて構成できない最小の郵便料金を問うものである。 
例えば、封筒には3枚の切手しか貼ることができないとする。使用可能な切手の額面が1円、2円、5円、15円の場合、12円までの金額は3枚までの切手で構成できる（例えば、4=2+2、8=5+2+1、11=5+5+1）。しかし、13円を構成するには少なくとも4枚の切手が必要となるため、13が解となる。 
数学的な定義.
数学的には、問題は次のように定式化される。 
特殊な場合.
"n" 種類、2枚の切手での解.
"n"種類を適切に選ぶと、2枚の切手での解は最大で
となる。
例えば、順に
となる。
2 種類、"h" 枚の切手での解.
2 種類を適切に選ぶと、"h"枚の切手での解は最大で
となる。
例えば、順に
となり、一般にformula_3の切手を用意することで最大化でき、その解は
と表せる。
3 種類、"h" 枚の切手での解.
3種類を適切に選ぶと、 "h" 枚の切手での解は最大で
となる。
"n" ≥ 20 のとき
とおくと
が "h" 枚の切手での最大の解を与え、その最大の解は
ここで "A", "B" は
となる
計算複雑性.
この問題は、 総当たりまたはバックトラッキングで |"V"|"m" の定数倍時間で解くことができる。ここで |"V"| は使用できる切手の額面の種類の数とする。したがって、封筒の容量 "m" が定数である場合、多項式時間で解ける問題である。容量 "m" が任意の場合、問題はNP困難である。