# Why is a Knapsack problem not an LP problem?

We know that LP can solve optimization problems that have linear constraints and linear objective functions.

A knapsack problem can be formulated into a linear objective function (because it is just a summation of Pi*Xi) and linear constraints (because it is just a summation of the items weights which should be <= the knapsack weight), so why can't we consider it an LP problem?

## 1 Answer

You can set up the knapsack problem as an integer linear program: To each item associate a 1/0 variable (include/exclude that item). Setting up the restrictions and the objective function from here is straightforward.

The point here is that the variables are restricted to be integers, while (regular) linear programming assumes real variables. They look similar, but are quite different beasts, computationally.

One successful technique to construct an approximate solution to the knapsack problem makes up a (continuous) linear programming problem, solve that one and tweaks the resulting values.