Why this conversion not being used to solve the backpack problem?

67 Views Asked by At

0-1 knapsack

$max $$\sum_{i=1}^{n} v_i x_i $

sobeject to

$\sum_{i=1}^{n} w_i x_i <= W $

$and x_i \in \{0, 1\} $

for all $i=1,2,...,n$

which restricts the number $x_i$ of copies of each kind of item to zero or one. Given a set of n items numbered from 1 up to n, each with a weight $w_i$ and a value $v_i$, along with a maximum weight capacity W,

in the 0-1 knapsack problem Why is the below conversion not being used to solve the backpack problem?

$max $$\sum_{i=1}^{n} v_i x_i $

sobeject to

$\sum_{i=1}^{n} w_i x_i <= W$

$x_i(x_i-1)=0$

$and x_i \in [-1,1]$

for all $i=1,2,...,n$

Why the problem is not solved in the time required for NLP, and when the number goes up, it requires a great deal of time to solve?