Why is the solution to the knapsack problem not considered as linear programming?

Question

Why is the knapsack problem not included in the category of linear programming algorithms, despite the fact that the statement of the knapsack problem seems similar to problems in linear programming?

Answer 1

A backpack can be written as an integer linear programming program. Unlike conventional linear programming, this problem requires that the variables in the solution be integers. It is known that linear programming is solvable in polynomial time, while integer linear programming is NP-complete.

Reader Exercise: Show that 3SAT can be reduced to integer linear programming.

General information: there are approximation algorithms for tasks such as MAX-3SAT (option 3SAT, where we want to maximize the number of satisfied offers). First you write MAX-3SAT as an integer linear program. Then you relax it to a linear program, removing the restriction of integers. Then you solve the linear program in polynomial time. Finally, given the real x _i ∈ [0,1], you round them to integers or create a random integer solution y _i , where the probability y _i = 1 is x _i .