小编G.E*_*.M.的帖子

当我想出一个似乎是解决它的通用算法时,我正在阅读子集和问题:

(defun subset-contains-sum (set sum)
    (let ((subsets) (new-subset) (new-sum))
        (dolist (element set)
            (dolist (subset-sum subsets)
                (setf new-subset (cons element (car subset-sum)))
                (setf new-sum (+ element (cdr subset-sum)))
                (if (= new-sum sum)
                    (return-from subset-contains-sum new-subset))
                (setf subsets (cons (cons new-subset new-sum) subsets)))
            (setf subsets (cons (cons element element) subsets)))))

"set"是不包含重复项的列表,"sum"是搜索子集的总和."子集"是缺点单元的列表,其中"car"是子集列表,"cdr"是该子集的总和.新的子集是在O(1)时间内从旧的子集创建的,只需将元素放在前面即可.

我不确定它的运行时复杂性是什么,但似乎随着每个元素"sum"的增长,"子集"的大小加倍,加上一个,所以在我看来至少是二次的.

我发布这个是因为我以前的印象是NP完全问题往往是难以处理的,并且通常希望最好的问题是启发式,但这似乎是一个通用的解决方案,假设你有CPU周期,总能给你正确的答案.有多少其他NP完全问题可以解决这个问题？