NP完全問題
部分和問題ともいう。整数 w 1 , ... , w n {\displaystyle w_{1},\ldots ,w_{n}} と目標値 W {\displaystyle W} が与えられる。このとき { w 1 , ... , w n } {\displaystyle \{w_{1},\ldots ,w_{n}\}} の部分集合 U {\displaystyle U} であって合計がちょうど W {\displaystyle W} となるものは存在するか?という問題。