# What's the big deal with the knapsack problem?

In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -> 234-tree -> red-black tree -> heap -> greedy algorithms -> dynamic programming.

And all the sudden, bam, there is this whole chapter on the knapsack problem. How is this problem different from weighted interval scheduling? Or longest common sub-sequence?

What's the importance of the knapsack problem?

• It's an arbitrary choice just like covering Red-Black but not AVL trees. Many problems would serve the same purpose of teaching you important concepts. – Raphael Nov 7 '14 at 8:37

## 2 Answers

The choice might indeed be arbitrary in a sense that with the knapsack problem, the instructor can introduce required concepts or techniques. But one could also argue that the knapsack problem is an important practical problem. In , Skiena analyzes 1503135 WWW hits recorded on the Stony Brook Algorithms Repository. Knapsack was the 18th most popular problem, and the 4th most needed algorithm implementation was for knapsack as well.

I think mainly the techniques that are covered in that section (dynamic programming and greedy algorithms) are very important.

There are several other properties. First of all, integral knapsack problem belongs to the famous class of problems called NP-complete (there is no known polynomial time algorithm for them), while the fractional knapsack is polynomial time solvable using a greedy algorithm. Thus, as an algorithm designer, you need to be able to recognize the difference between the nature of these two problems in order to solve them.

Also, one interesting point is that, although the dynamic programming technique is psuedo-polynomial time for the integral knapsack problem, it can be run exponentially in general case.