4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Nov 7 '14 at 8:37
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.