部分和問題
提供: miniwiki
部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論における問題で、与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題である。NP完全であることが知られている。
この問題は、分割問題 (Number Partitioning) の一般形でもある。分割問題とは、与えられた n 個の整数 a1,...,an を二つの集合に分け、各々の集合内の数の和がもう一方の集合内の数の和と等しくなるようにできるかどうかを判定する問題である。この問題も、NP完全であることが示されている。
部分和問題は、ナップサック問題に含まれるため、動的計画法等の手法で解くことができる。（詳しくは、ナップサック問題の項を参照。）
問題例
- 問題1: {1,3,7,10,13} の部分和で、和が 21 になるものは存在するか？
- 答え: 存在する。{1,7,13}
- 問題2: {2,4,6,8,10} の部分和で、和が 19 になるものは存在するか？
- 答え: 存在しない。（偶数の和は偶数にしかならないから。）