algorithm - 为什么解决背包问题不被视为线性规划？

Question

尽管背包问题陈述似乎与线性规划中的问题相似，但为什么不将背包问题包含在线性规划算法的类别中？

Answer 1

背包可以写成整数线性规划程序。与正常的线性规划不同，这个问题要求解中的变量是整数。众所周知，线性规划可以在多项式时间内求解，而整数线性规划是 NP 完全的。

读者练习：证明 3SAT 可以简化为整数线性规划。

琐事：有一些近似算法可以解决诸如 MAX-3SAT（3SAT 的变体，我们希望最大化满足子句的数量）等问题。首先你把 MAX-3SAT 写成一个整数线性程序。然后，通过消除整数限制，将其放松为线性规划。然后，您在多项式时间内求解线性程序。最后，给定实数 x _i ∈ [0,1]，将它们四舍五入为整数，或生成随机整数解 y _{i ，其中 y i} = 1 的概率为 x _i。