This post is on the Knapsack algorithm which does the following. You have a list of items each with a value and weight. You have a total capacity as limit. You have to take as many items to increase value within the limit. A good example, similar to the one given by MIT Professor John Guttag (in open courseware) is, you break into a bank vault with a sack which can hold 100Kg of weight. You are faced with a pile of gold coins, million dollar bonds, a huge stack of Marlboro cigarettes, stacks of red bull and Heineken. How much of each should you take given your limit? A better example is you are going to Mars and your allotment in the shuttle is 400Kg and you have to take items that are valuable in that limit.
The Algorithm is recursive but, uses memoization to cut short the search through the solution tree. i.e for a pair (number of things remaining to take from, remaining capacity) i.e you have 5 more things to take from and weight limit is now 30Kg then, what do you take for this? If this is already solved in the recursion somewhere we use that, instead going down to that. This is where memoization comes in and Python dictionary is well suited for this. So, you have sub problems and find optimal solutions to those problems and solve the parent problem.
The result of the algorithm is a pair (V, I) where V is the accrued value of items we decided to take. I is the list of items we decided to take.
Knapsack 0/1 Algorithm Pseudo code:
knapsack(<L: list of items>, <W: weight limit now>, <S: solutions accumulated over sub-problems so far>)
{
IF S is empty i.e first call THEN
Initialize S the set/dictionary to hold solutions to sub-problems
IF combination of (L, W) is already in S THEN
(V,I) for this sub-problem = S(L, W)
ELSE IF L is empty and W is 0 THEN
(V, I) is (0, nothing)
ELSE IF we take the first item on list and its weight, when added, exceeds the limit THEN
(V,I) = knapsack(L - first item at this call, W, S)
ELSE
/* What we do here is. We assume we take the first item. Then what is (V,I) for the remaining
walks. Also, what is the result (V,I) id we don't take the item at this point. Choose which
ever solution that maximises the value.
*/
We assume we take the first item of the list.
Let V1 = Value of first item + (V, I) for knapsack(L - first item, W - weight of first Item, S)
We also find (V2, I) if we don't take the item.
i.e (V2, I) for knapsack(L - first item, W, S)
IF V1 is better than V2 THEN
go with that result (V1, I)
ELSE
go with the other result (V2, I)
Add the corresponding result (V, I) to S
}
Sample with the following items. <Item Name, Weight, Value>
('Gold Biscuits', 20, 100)
('Heineken', 2, 30)
('Marlboro', 1, 10)
('Currency in $10 bills', 10, 10)
('Currency in 50$ bills', 45, 40)
('Million$ Govt Bonds', 1, 1000)
('Diamonds', 25, 80)
('Lays Chips', 1, 4)
('RedBull Cans', 20, 35)
('Predictions on WallStreet', 1, 200)
('Key Combination of Vault', 1, 200)
('Harry Potters List of real life Spells', 2, 1)
Sample Output: As you can see the program takes the things of value :))
Solution Python Code: Is available at
https://drive.google.com/folderview?id=0BxhHg0qy5gi4TkpuTHQ4OWZGYnc&usp=sharing
References:
1. MIT Open courseware on Introduction to Computer Science and Programming, Prof John Guttag
