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?

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.

StackExchange Computer Science Q#32804, answer score: 4