为什么要解决背包问题。不被视为线性编程？

Question

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

Answer 1

背包可以写成整数线性规划程序。与一般的线性规划不同，这个问题要求解决方案中的变量是整数。已知线性规划在多项式时间是可解的，而整数线性规划是NP完全的。

读者练习：显示3SAT可以简化为整数线性规划。问题：MAX-3SAT（我们希望最大化满意子句数量的3SAT变体）存在近似算法。首先你写一个整数线性程序MAX-3SAT。然后，你放松它去线性化程序，通过删除整数限制。然后，你用多项式时间求解线性程序。最后，给定的实X _我∈[0,1]，将它们舍入到整数，或产生随机整数解y _我其中y _我 = 1的概率为x _我。