algorithm - 减少 0-1 背包概率。到 SAT 问题

Question

有没有办法减少0-1 knapsack problem到 SAT problem在联合范式中？

Answer 1

您始终可以计算出实现加法器和比较器所需的数字电路，然后将其结果转换为合取范式。您可以通过构造代表小部分电路输出的中间变量，将电路转化为 CNF 形式，而无需以指数方式扩展它们。

电路的每个节点相当于 a=f(b, c)，其中 a 是输出，b 和 c 是输入，f 是一些简单的函数，例如 & 或 |。您可以创建一个仅当 a 确实是 f(b, c) 的结果时才为真的 CNF 函数，并且它不会太笨拙，因为它是仅基于三个变量的函数。

您可以将任何电路重写为 a=f(b, c) 形式的大量项，而对于这些的 CNF 版本，您所要做的就是将它们加在一起。假设您想要解决输出为真的问题，那么您只需将输出变量作为那个大 AND 的最后一个组成部分。