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?

  • 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

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.

  • $\begingroup$ I think that evaluation of Skiena is not really reliable. The importance of a problem cannot be evaluated I believe. Even if we decide to evaluate it, we should use some better metrics; internet visitor hits are not a very good measure. $\endgroup$ – orezvani Nov 8 '14 at 3:06
  • $\begingroup$ @emab You only say you think it's not reliable, and moreover that the importance of a problem cannot be evaluated. You provide no arguments. (I don't argue either way, I'm just reporting on someone's published work.) $\endgroup$ – Juho Nov 9 '14 at 8:19
  • $\begingroup$ The first argument is about the reliability of internet hits. If you look more closely, you will see that lot's of people who search the net for these known problems (and hit their web site) are trying to find answer to their assignments or getting ready for job interviews and many other non-relevant reasons. $\endgroup$ – orezvani Nov 9 '14 at 8:38
  • $\begingroup$ The second argument is that I believe it's not a good idea to evaluate the importance of a problem. The word "importance" has a very wide meaning. One problem may have only one application, but that application is very critical; while another problem may have lot's of small applications. On the other hand, the importance of problem can be determined in terms of their impact on other sciences or future research and many other aspects (not just the number and capital of applications) $\endgroup$ – orezvani Nov 9 '14 at 8:42
  • $\begingroup$ @emab I agree there could definitely be better ways of evaluating the importance of a problem than what is done in [1]. $\endgroup$ – Juho Nov 9 '14 at 8:56

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.


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.