The Knapsack Problem
bertolami.com
bertolami.com
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.
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.
https://github.com/mgraczyk/DiscreteOptimization/blob/master/knapsack/speed_up/solve_it.cpp
https://www.coursera.org/course/optimizationHaving 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.
Particularly tree and graph manipulations can be very common tasks depending on your job description.
Regardless, if you want to reference that specific article, and only that article, I can do that as well. It happens to refute your very own point:
"Now, I freely admit that programming with pointers is not needed in 90% of the code written today, and in fact, it's downright dangerous in production code. OK. That's fine. And functional programming is just not used much in practice. Agreed.
[...]
But beyond the prima-facie importance of pointers and recursion, their real value is that building big systems requires the kind of mental flexibility you get from learning about them, and the mental aptitude you need to avoid being weeded out of the courses in which they are taught. Pointers and recursion require a certain ability to reason, to think in abstractions, and, most importantly, to view a problem at several levels of abstraction simultaneously. And thus, the ability to understand pointers and recursion is directly correlated with the ability to be a great programmer."
Finally, you tacitly assumed you knew which article I had in mind, and you were wrong, not that it matters since I wasn't actually trying to reference a specific article. I was referring to The Guerrilla Guide to Interviewing. He offers example questions like "reverse a linked list" or "detect loops in a tree structure" -- concepts and problems which are clearly not relegated only to C.
1) Joel believes that pointers and recursion are concepts that require a way of thinking about higher order abstractions that correlates well with being a good programming hire. So it would make sense if we agreed with him to ask questions about pointers & recursion in interviews, even if we don't believe that pointers or recursion are used often in the settings we are hiring for. 2) Many people have built long careers without using recursion, but that doesn't refute the premise because it doesn't speak to the higher order abstractions assumption. Further, in the modern world recursion is no more or less likely to be used than pointers (which would be shocking at one point in the industry) as pointers also are not common. 3) The central assumption Joel basis his argument on is that pointers and recursion are interesting because reasoning well about them requires a higher level of abstraction. That higher level of abstraction simply does not exist with Java style references. So asking about references, while maybe useful in other contexts, doesn't have the benefits Joel is arguing for in the same way as pointers. 4) To relate this back to the article, A) is understanding dynamic programming indicative of some central mental type that will correlate with a good programmer? B) Does asking questions about the Knapsack problem suss out that understanding. I suspect, but can't prove that the answers are A) not like pointer/recursion understand and B) absolutely not.
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.
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.
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.
If you want a really challenging problem, look into the multiple knapsack problem.
Edit: Note, n^2 is generally far better than 2^n so it's still useful even if it's slow.
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
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.
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.
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.
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.
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.
Now we have to ask ourselves a few things A) which of us is correct about which is more intuitive and B) does being intuitively good at the knapsack problem imply anything about being intuitive at dynamic programming and C) does being intuitively good at dynamic programming or the knapsack problem have any correlation between good hires.
"This feels like a dynamic programming/max-flow-min-cut/linear programming problem. I'd formalize it, look it up in a textbook, like Chvatal, or on Wikipedia, and find the precise problem class. Then I'd look for an appropriate code. Or, maybe go back to the problem origin and see if the actual problem maps in to one of the more general classes I just looked up."
Perhaps much more realistic an answer than some poking around on the whiteboard by someone who may have studied this in school anyway. Having a feeling for problems that should already be well-studied/solved can be more valuable than bumbling on to the solution after a few minutes.
There. Now, instead of asking for CS theory from candidates in the most hostile imaginable setting (that's what a job interview is: hostile) and telling yourself a cute little story about how you're determining how candidates handle interesting problems that require them to consult the literature: you actually allow the candidate to demonstrate how they would do that.
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?)