Does this actually answer the stated problem of "deciding the subset of items to pack"?<p>Looking at the solution table I can see that there are two possible solutions, and I can see a max <i>value</i> of 6. But I can't see how v[4,3] implies packing objects 1 and 3.
I wrote a solution using this table building DP algorithm a few years ago.<p><pre><code> https://github.com/mgraczyk/DiscreteOptimization/blob/master/knapsack/speed_up/solve_it.cpp
</code></pre>
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.<p><pre><code> https://www.coursera.org/course/optimization</code></pre>
For those of you planning on interviewing...<p>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.
Off 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.
Interesting problem. If you play a game like elder scrolls skyrim or oblivion, you run into this problem literally.<p>Without reading, I already knew the solution.<p>To solve it in your head: sort items by most value/weight efficient to least efficient.<p>Then take as much as you can until you're full.<p>(in a game like elder scrolls oblivion, that means jewelry first, and silver vases last)<p>-----<p>edit: I am mistaken, as some of the below comments accurately pointed out.
May be relevant: there is a cool game - knapsack on a radial graph, with Scala source code.
<a href="http://krishnanraman.github.io/scala-js/examples/helloworld/helloworld.html" rel="nofollow">http://krishnanraman.github.io/scala-js/examples/helloworld/...</a>
This 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.<p>Edit: Note, n^2 is generally far better than 2^n so it's still useful even if it's slow.
I 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.
This is a domain where Unconventional Computing seems to work well, e.g., "DNA computing" through its massively parallel processing capabilities.