部分ぶぶん和わ問題もんだい

部分ぶぶん和わ問題もんだい（ぶぶんわもんだい）は、計算けいさん複雑ふくざつ性せい理論りろん・暗号あんごう理論りろんにおける問題もんだいで、与あたえられた n 個この整数せいすう a₁,...,a_n から部分ぶぶん集合しゅうごうをうまく選えらんで、その集合しゅうごう内ないの数かずの和わが与あたえられた数かず N に等ひとしくなるようにできるかどうかを判定はんていする問題もんだいである。NP完全かんぜんであることが知しられている。

部分ぶぶん和わ問題もんだいは、分割ぶんかつ問題もんだい (Number Partitioning) の一般いっぱん形がたでもある。分割ぶんかつ問題もんだいとは、与あたえられた n 個この整数せいすう a₁,...,a_n を二ふたつの集合しゅうごうに分わけ、各々おのおのの集合しゅうごう内ないの数かずの和わがもう一方いっぽうの集合しゅうごう内ないの数かずの和わと等ひとしくなるようにできるかどうかを判定はんていする問題もんだいである。分割ぶんかつ問題もんだいも、NP完全かんぜんであることが示しめされている。

たとえば、「{1,3,7,10,13} の部分ぶぶん和やわで、和わが 21 になるものは存在そんざいするか？」であれば存在そんざいする（{1,7,13}である）、が答こたえである。また「{2,4,6,8,10} の部分ぶぶん和やわで、和わが 19 になるものは存在そんざいするか？」であれば、存在そんざいしない（どんな部分ぶぶん和わも偶数ぐうすうにしかならない）、が答こたえである。

部分ぶぶん和わ問題もんだいは、ナップサック問題もんだいに含ふくまれるため、動的どうてき計画けいかく法ほう等ひとしの手法しゅほうで解とくことができる。（詳くわしくは、ナップサック問題もんだいの項こうを参照さんしょう。）