我正在研究這個問題：該子集和問題需要輸入一個組X = {x1, x2 ,…, xn}的n整數和另一個整數K。問題是，以檢查是否存在一個子集X'的X，它的元素之和為K，并發現該子集，如果有任何。例如，如果X = {5, 3, 11, 8, 2}和K = 16則答案是YES因為子集X' = {5, 11}的總和為16。為運行時間至少為的子集和實現一個算法O(nK)。注意復雜性O(nK)。我認為動態編程可能會有所幫助。我發現了指數時間算法，但沒有幫助。有人可以幫我解決這個問題嗎？
3 回答
哈士奇WWW
TA貢獻1799條經驗 獲得超6個贊
我建議閱讀Wiki的算法。該算法存在于此，有關該解決方案，請參閱偽多項式時間動態規劃解決O(P*n)方案，該解決方案不是多項式時間，在（p，n）中是多項式，但在n + log P（輸入大?。┲胁皇嵌囗検?，并且因為P可以像2 ^ n這樣的非常大，解P * n =（2 ^ n）* n通常不是多項式時間解，但是當p受n的某些多項式函數限制時，就是多項式時間算法。
這個問題是NPC，但是有一個Pseudo polynomial time算法，屬于weakly NP-Complete問題，也有Strongly NP-Complete問題，這意味著pseudo polynomial time除非P = NP，否則找不到任何算法，并且這個問題不在此問題范圍內，所以以某種方式很容易。
我說的是盡可能簡單，但這不是完全NP完全或完全NP完全問題的確切定義。
添加回答
舉報
0/150
提交
取消