为什么要解决背包probl。不被认为是线性规划？ [英] Why solving Knapsack probl. is not considered as linear programming?

问题描述

为什么不是下的类别包括背包问题的线性规划算法的，尽管事实上，在背包问题声明似乎类似的问题的线性规划的？

Why isn't the knapsack problem included under the category of linear programming algorithms in spite of the fact that the Knapsack problem statement seems similar to the problems in linear programming.?

推荐答案

背包可以写成的整数线性规划的程序。不同于一般的线性规划，这个问题需要，在溶液中的变量是整数。线性规划被称为是在多项式时间，而整数线性规划是NP完全问题。

Knapsack can be written as an integer linear programming program. Unlike normal linear programming, this problem requires that variables in the solution are integers. Linear programming is known to be solvable in polynomial time, while integer linear programming is NP-complete.

练习读者：表明3SAT可以降低到整数线性规划

Exercise for the reader: show that 3SAT can be reduced to integer linear programming.

花絮：有近似算法的问题如MAX-3SAT（3SAT的变体，我们要最大限度地满足子句的数目）。首先，你写的MAX-3SAT为整数线性规划。然后，你的放松的它的线性规划，通过删除整数限制。然后，您解决在多项式时间线性程序。最后，由于真正的X <子>我∈[0,1]，则四舍五入他们整数，或生成随机整数解y <子>我其中的是<子>概率我 = 1为x <子>我。

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 x_i ∈ [0,1], you round them to integers, or generate random integer solution y_i where probability of y_i = 1 is x_i.

这篇关于为什么要解决背包probl。不被认为是线性规划？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！