6 ms·
The Knapsack Problem
- alta22433 12y agoI was asked this on a recent programming interview. As a recent college graduate, I'm not sure this is a fair question to ask under that context given the complexity of the problem. Nice article though.
- tptacek 12y agoUnless the role you're being interviewed for is "Algorithm Designer", this is a really stupid interview question.
- crazypyro 12y agoIt's one of those stupid questions where you either have seen it before and use memorization to pull it up or you flounder because you can't come up with a new algorithm on the spot.
- gt565k 12y agoUmm, the knapsack problem was covered extensively in my Design and Analysis of Algorithms class as part of the dynamic programming section. I honestly felt that this class was the most useful and relevant out of all CS classes I took as an undergraduate student. Dynamic programming is very useful, and this problem is a classic. It's asked quite a bit in interviews.
- benihana 12y agoSeems like a great question to ask if you want to find out if a candidate has taken courses similar to you or has seen this problem before.
- kajecounterhack 12y agoMaybe unintentional (and not saying if this is good or bad) but it is a little self-selecting: by asking you can tell "Ok so candidate x has had this kind of educational background and at least has heard of the name which might correlate with traits y or z"
- gt565k 12y agoor knows about space-time complexity and why dynamic programming is important when dealing with problems such as this that might involve large data sets...
- norseboar 12y agoThere seems to be a connotation that asking a question "just to see if the candidate has seen the problem before" is bad, for some reason (apologies if this connotation wasn't there). This is actually a very important thing to look for in an interview. While it might not be "fair" in the sense that not all smart people can effectively answer it, it's absolutely effective to sort out who has a good grasp of algorithms (and memoization in particular). There are too many smart people out there to interview just for that; you've got to look for existing knowledge too.
- kasey_junk 12y agoThere are definitely times in your hiring process when you want to bias towards people with existing knowledge. The problem with this particular question is that it doesn't imply any in depth knowledge of dynamic programming. It is literally something you can see in a survey of algorithms course. So by asking this question, I suspect you are biasing towards people who have recently taken a survey of algorithms course. I'm having a hard time envisioning the hiring situation where I'd want that bias.
- pushrax 12y agoThe knapsack problem is the canonical dynamic programming problem. Any decent combinatorics class should touch on these concepts at some point.
- tptacek 12y agoAnd that makes it a good interview question because...
- pushrax 12y agoIt's a good interview question for the same reason any question is: it allows you to see how the interviewee thinks and approaches a problem (if they haven't seen it before). If they have seen it before, you can see how well they can externalize their knowledge.
- kasey_junk 12y agoNot all questions are good interview questions. For any question you ask, you need to know A) why are you asking it? B) what does it bias your hiring pipeline towards/against? C) what is a good answer to the question? D) how would a perspective employee come to that answer? and most importantly E) given limited resources available to hiring, are there better questions I could be asking. This is a question that is trivial to answer if you remember basic dynamic programming examples. It is nearly impossible to come up with the "right" answer without it. I'm trying very hard to understand what sort of hiring situation would be interested to know if someone understood basic dynamic programming (without knowing more advanced topics) or could suss it out on their own.
- pushrax 12y agoFor sure, it's definitely not the ideal interview problem. My intended argument was just that it's not an unfair interview problem. As an aside, I don't think it's that unlikely to come up with a dynamic programming solution without prior knowledge of the general problem class. It's a pretty intuitive idea.
- kajecounterhack 12y agoI think it's a fair question in that it's taught in most algos classes and they don't usually ask it outright, they ask for some variation and want to see that you can handle the task of at least recognizing the problem, and then (hopefully) translating. Or at least getting close. Also there are a couple of ways to approach this, I think it really helps elucidate how a person tackles a tricky problem upfront (does the person try to write the recurrence out first? does the person do the exponential recursive solution and then memoize? does the person visualize this like a graph, a table, or something else?)
- codehero 12y agoOff the top of my head I look at it as a graph 2 coloring problem. The graph starts out with 1 node per item and zero edges. If we think two items will be in the same set (either in the knapsack or out) we merge the nodes and their weight and value combine into the new node. We draw edges between two nodes if their combined weights exceed the knapsack capacity. When we recurse out of our merge choice, we also draw an edge between the two nodes that composed the merge. Our recursion depth ends at a clique.
- Retric 12y agoThis still can easily be worse than n^2 if your weight is significantly higher than your number of objects. Aka max weight of 10,000 and 1,000 objects. Edit: Note, n^2 is generally far better than 2^n so it's still useful even if it's slow.
- alta22433 12y agoYeah, seems like the article implies an upper bound of 2^n for a greedy solution, so your example would be pretty bad with a worst case of 2^1000?
- Retric 12y agoMy example would be 1000 objects * 10,000 weights = 10,000,000 options. Which is much better than 2^(1000) ~= 10^300 for calculating every possibility, but still worse than n^2. For it to be worse you would need say 10 objects and 10,000 for max weight. so 2^n = 1024 vs n * k = 10 * 10,000 = 100,000
- Domenic_S 12y agoDoes this actually answer the stated problem of "deciding the subset of items to pack"? Looking at the solution table I can see that there are two possible solutions, and I can see a max value of 6. But I can't see how v[4,3] implies packing objects 1 and 3.
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- platunit2 12y agoAuthor here -- great point! I've updated the problem statement to make it more clear :) In this case, the article is simply asking "what is the highest value that you can achieve" Thanks for the feedback! :)
- Retric 12y agoYou can read the chart backwards to get an answer. Check 2 vs 3 @4lb. That's constant so 3 is not in there. Check 1 vs 2 @4lb. It changes so ob2 is in there. Now 3 weighs 2lb so look at 4lb - 2lb(ob3) = 2lb max weight. Check 0 vs 1@2lb. That's increasing so object 1 is in there 2lb - 1lb (ob1) = 1lb max. Check 0 @1lb that's greater than zero so object 0 is also in there. Thus, the solution is objects 0,1,2 but not 3. PS: Note, this only finds one solution there might be several. You can quickly find them with this chart but it's somewhat more complex. You would be looking for places where the max value does not change from the previous row, but the max value in the same row - the object weight = the max value - the object value.
- chris_va 12y agoFor those of you planning on interviewing... Having done interviews for a large tech firm, dynamic programming questions are a favorite for weeding out candidates. Anecdotally, it correlates rather well with problem solving skills.
- nilkn 12y agoYears ago, Joel Spolsky wrote that it was critical for any interview to at least touch on pointers/references and recursion. I think at many major tech companies dynamic programming is included in that bag as well.
- JoeAltmaier 12y agoAnd yet, I can count on one finger the number of recursive algorithms I have ever, ever used in 20 years of programming.
- kajecounterhack 12y agoThat's interesting, YMMV cuz I've been full-time for a little over a year and I've already written (at least) three. Particularly tree and graph manipulations can be very common tasks depending on your job description.
- kasey_junk 12y agoAnd I'm sure you can find people who have programmed extensively for the last 20 years and have not needed to deal with pointers directly.
- nilkn 12y agoI'd be pretty impressed if someone had programmed extensively for two decades and yet had never dealt with references of some kind. It doesn't have to explicitly be pointers in C.
- 12y ago
- pramalin 12y agoMay be relevant: there is a cool game - knapsack on a radial graph, with Scala source code. http://krishnanraman.github.io/scala-js/examples/helloworld/helloworld.html http://krishnanraman.github.io/scala-js/examples/helloworld/...
- hayksaakian 12y agoInteresting problem. If you play a game like elder scrolls skyrim or oblivion, you run into this problem literally. Without reading, I already knew the solution. To solve it in your head: sort items by most value/weight efficient to least efficient. Then take as much as you can until you're full. (in a game like elder scrolls oblivion, that means jewelry first, and silver vases last) ----- edit: I am mistaken, as some of the below comments accurately pointed out.
- crazypyro 12y agoThis is a "false" solution, in the sense that you can create a large number of scenarios where just taking the most value/weight efficient item, regardless of the relationship between the items, will result in a non-optimal solution. e.g. 2 Silver coins worth 4 and weighs 2. 1 Gold coin worth 5 and weighs 3. Silver slightly more efficient, but if your bag size is 5, the obvious solution is 1 gold + 1 silver coin worth 9, where as your "algorithm" would give 2 silver coins weighing 8, worth 8.
- hayksaakian 12y agoI guess my solution was more approximate but easier to reason about. You're right, it falls apart on the borders of max capacity.
- shliachtx 12y agoThat's not necessarily the case. For example: If you have 10[s] (units of space) in your knapsack, and you have 3 items in front of you the first with two with 5[s] and 4[v] (units of value) each, and the third with 6[s] and 7[v], the best solution would be to take the first two, even though they have a lower [s]/[v] ratio, because you will end up with 1[v] more.
- hayksaakian 12y agoyou are correct, i was mistaken.
- ekr 12y ago
- mgraczyk 12y agoI wrote a solution using this table building DP algorithm a few years ago. https://github.com/mgraczyk/DiscreteOptimization/blob/master/knapsack/speed_up/solve_it.cpp This was part of an assignment for a Coursera Discrete Optimization course created by The University of Melbourne. It's a great course and I recommend it to anybody who wants to hone their understanding of dynamic programming and solving computationally expensive problems. https://www.coursera.org/course/optimization
- hkon 12y agoI took this course as well. Really interesting. And a really cool way to submit programming assignments and get instant feedback if you "passed" or not. Some years since I was in school, this might be the de-facto way of doing it now.
- lunz 12y agoThis is a domain where Unconventional Computing seems to work well, e.g., "DNA computing" through its massively parallel processing capabilities.