子集和問題
維基百科,自由的 encyclopedia
子集和問題(英語:Subset sum problem),又稱子集合加總問題,是計算複雜度理論和密碼學中一個很重要的問題。問題可以描述為:給一個整數集合,問是否存在某個非空子集,使得子集內中的數字和為某個特定數值。例:給定集合{−7, −3, −2, 5, 8},是否存在子集和為0的集合?答案是YES,因為子集{−3, −2, 5}的數字和是0。這個問題是NP完全問題,且或許是最容易描述的NP完全問題。
此條目沒有列出任何參考或來源。 (2015年1月22日) |
一個等價的問題是:給一個整數集合和另一個整數s,問是否存在某個非空子集,使得子集中的數字和為s。子集合加總問題可以想成是背包問題的一個特例。