use*_*957 11 algorithm knapsack-problem linear-programming
尽管Knapsack问题陈述似乎与线性规划中的问题类似,但为什么线性规划算法类别中不包括背包问题？
sdc*_*vvc 12
背包可以写成整数线性编程程序.与普通线性编程不同,此问题要求解决方案中的变量是整数.已知线性编程在多项式时间内是可解的,而整数线性编程是NP完全的.
为读者练习:表明3SAT可以简化为整数线性编程.
琐事:有一些问题的近似算法,例如MAX-3SAT(我们希望最大化满足条款数量的3SAT的变体).首先,您将MAX-3SAT写为整数线性程序.然后,通过删除整数限制,将其放宽到线性程序.然后,在多项式时间内求解线性程序.最后,给定的实X 我 ∈[0,1],则舍入他们的整数,或者产生随机整数解y 我其中y的概率我 = 1为x 我.