A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete.
O soluție pentru problema rucsacului la orice procent fix din soluția optimă poate fi calculată în timp polinomial, dar găsirea soluției optime este NP-completă.