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

Question

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

algorithmlinear-programmingknapsack-problem

11

尽管背包问题看起来与线性规划问题相似，为什么背包问题没有被归类为线性规划算法的一种呢？

- user1543957

1

@yes123 在线性规划中，线性的是约束条件，而不是时间。 - fgb

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sdcvvc · Accepted Answer

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

读者练习：展示3SAT可以归约到整数线性规划问题。

趣闻：对于MAX-3SAT等问题，有近似算法（一种3SAT变种，其中我们想要最大化满足子句的数量）。首先将MAX-3SAT写成整数线性程序，然后通过去除整数限制来“松弛”它成为线性规划，接着在多项式时间内解决线性规划。最后，给定实数x_i∈ [0,1]，将它们四舍五入为整数，或生成概率为x_i的随机整数解y_i。