为什么不是线性规划算法 ，尽管事实上该类别下包括背包问题背包问题声明似乎类似于线性规划的问题？
Answer 1:
背包可以写为一个整数线性规划程序。 不同于一般的线性规划，这个问题需要在解决变量均为整数。 线性规划被称为是在多项式时间内可解，而整数线性规划是NP完全问题。
读者练习：表明3SAT可以降低到整数线性规划。
花絮：对于如MAX-3SAT（3SAT的一个变种，我们希望最大限度地满足条款的数量）问题的近似算法。 首先，你写MAX-3SAT为整数线性规划。 然后，你把它放宽到线性规划，通过移除整数限制。 然后，您解决在多项式时间线性程序。 最后，给定的实X I∈[0,1]，则舍入他们的整数，或者产生随机整数解y i其中Y的概率I = 1是X I。
文章来源: Why solving Knapsack problem is not considered as linear programming?
