子集和問題, 此條目没有列出任何参考或来源, 2015年1月22日, 維基百科所有的內容都應該可供查證, 请协助補充可靠来源以改善这篇条目, 无法查证的內容可能會因為異議提出而移除, 英語, subset, problem, 又称子集合加總問題, 是計算複雜度理論和密碼學中一個很重要的問題, 问题可以描述为, 給一個整數集合, 問是否存在某個非空子集, 使得子集内中的數字和為某个特定数值, 給定集合, 是否存在子集和为0的集合, 答案是yes, 因為子集, 的數字和是0, 這個問題是np完全问题, 且或許是最容易描. 此條目没有列出任何参考或来源 2015年1月22日 維基百科所有的內容都應該可供查證 请协助補充可靠来源以改善这篇条目 无法查证的內容可能會因為異議提出而移除 子集和問題 英語 Subset sum problem 又称子集合加總問題 是計算複雜度理論和密碼學中一個很重要的問題 问题可以描述为 給一個整數集合 問是否存在某個非空子集 使得子集内中的數字和為某个特定数值 例 給定集合 7 3 2 5 8 是否存在子集和为0的集合 答案是YES 因為子集 3 2 5 的數字和是0 這個問題是NP完全问题 且或許是最容易描述的NP完全問題 一個等價的問題是 給一個整數集合和另一個整數s 問是否存在某個非空子集 使得子集中的數字和為s 子集合加总问题可以想成是背包問題的一個特例 动态规划解法 编辑用动态规划的方法 能够以伪多项式时间解决子集合加总问题 我们假定输入序列为 x1 xn我们需要判断是否存在某个非空子集 使得子集中的数字和为0 我们序列中负数的和为N 正数的和为P 定义函数Q i s 它的涵义为 是否存在x1 xi的非空子集 使得子集中的数字和为s子集合加总问题的答案即为Q n 0 显然 如果s lt N或者s gt P 则Q i s false 因此无需记录这些值 我们把Q i s 的值保存在数组中 其中1 i n且N s P 接下来使用循环来填充数组 首先 对于N s P 设定 Q 1 s x1 s 随后 对于i 2 n和N s P 设定 Q i s Q i 1 s 或 xi s 或 Q i 1 s xi 算法运行的总时间为O n P N 对算法加以改动 即可返回和为0的子集 在计算复杂度理论中 这种解法需要的时间并不算多项式时间 这是因为P N同输入大小并不成线性关系 原因在于输入大小仅仅取决于表达输入所需要的位元數 算法的时间复杂度同N与P的值成线性关系 而它们的值与表达它们所需的位元數成幂关系 取自 https zh wikipedia org w index php title 子集和問題 amp oldid 76094106, 维基百科,wiki,书籍,书籍,图书馆,