部分和問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 部分和問題の意味・解説 

部分和問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/04/14 06:02 UTC 版)

ナビゲーションに移動 検索に移動

部分和問題(ぶぶんわもんだい)は、計算複雑性理論暗号理論における問題で、与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題である。NP完全であることが知られている。

部分和問題は、分割問題 (Number Partitioning) の一般形でもある。分割問題とは、与えられた n 個の整数 a1,...,an を二つの集合に分け、各々の集合内の数の和がもう一方の集合内の数の和と等しくなるようにできるかどうかを判定する問題である。分割問題も、NP完全であることが示されている。

たとえば、「{1,3,7,10,13} の部分和で、和が 21 になるものは存在するか?」であれば存在する({1,7,13}である)、が答えである。また「{2,4,6,8,10} の部分和で、和が 19 になるものは存在するか?」であれば、存在しない(どんな部分和も偶数にしかならない)、が答えである。


部分和問題は、ナップサック問題に含まれるため、動的計画法等の手法で解くことができる。(詳しくは、ナップサック問題の項を参照。)




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「部分和問題」の関連用語

部分和問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



部分和問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの部分和問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS