The best articulation of the Knapsack problem that I have encountered is that in the context of Indiana Jones.
Assume Indiana Jones is trying to escape a collapsing treasure cave. The cave is littered with many precious items, golden goblets, statues, coins .. you name it. Indiana has a knapsack to collect some of the treasure items and tow it along with him. The challenge is that his knapsack can only carry so much load and Indiana wants to make the best choices so that he carries the maximum value of artifacts in his knapsack.
More generally, the above problem manifests itself in many day to day challenges. Some of them being:
- Assuming we have certain time at hand and a list of tasks in our todo list. Each task taking a forecasted amount of time. What is the subset of tasks that need to be chosen so that we make the best use of the time at hand.
- Given a chess board at a certain stage, which is the next best move
- http://people.cs.clemson.edu/~bcdean/dp_practice/ contains a list of problems of similar nature
To the uninitiated, at the face of it the problem will sound simple. To the moderately initiated, recursive backtracking would sound ideal to solve these problem. It is only the initiated who will understand the time complexity of tree traversal - making simple recursive, full tree traversal algorithms difficult to use even at data sets exceeding 10 elements.
A good treatise on the Knapsack problem can be found here : http://en.wikipedia.org/wiki/Knapsack_problem
If you want a (very very) small library, encapsulating the algorithm for use in your project, you can check out the code at my GitHub site
https://github.com/deb-sandeep/BranchAndBound
If you need any help with the code, please drop me a note..
No comments:
Post a Comment