为什么背包问题不属于线性规划算法尽管背包问题陈述看起来与中的问题相似线性规划?
背包可以写成整数线性规划程序。与普通的线性规划不同，该问题要求解中的变量是整数。已知线性规划可在多项式时间内求解，而整数线性规划是 NP 完全的。
读者练习：证明 3SAT 可以简化为整数线性规划。
Trivia: there are approximation algorithms for problems such as MAX-3SAT (a variant of 3SAT where we want to maximize the number of satisfied clauses). First you write MAX-3SAT as an integer linear program. Then, you relax it to linear program, by removing the integer restriction. Then, you solve the linear program in polynomial time. Finally, given real xi ∈ [0,1], you round them to integers, or generate random integer solution yi where probability of yi = 1 is xi.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
