[Solved]: What's the big deal with the knapsack problem?

Problem Detail: 

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?

Asked By : John Swoon

Answered By : Juho

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 [1], 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.

---

[1] Skiena, Steven. "Who is interested in algorithms and why?: lessons from the Stony Brook algorithms repository." ACM SIGACT News 30.3 (1999): 65-74.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32804