Feb 3, 2012

Dynamic programing and the knapsack problem.

As I always forget the structure of a dynamic algorithm, this note is a reminder of the key idea behind the dynamic knapsack programming.

The knapsack problem is when we consider a large set of object having different size and value, knowing that the knapsack have a fixed size (S) the objective is to pack the subset that give the highest value ( to simplify the problem , lets say it Thief that have to choose which valuables to put in his bag)

Let vi be the value of the object i and si the size of the object i.

1- The first key idea is that the items are sorted by efficiency with is the price of an item divided by its size , in a decreasing order (most efficient to the worst efficient).

P1/s1 >= p2/s2 >= p3/s3 .......

2- The second key idea is related to space of solution, where the set of object to be considered is incremented gradually, following the order of the efficiency of objects. So N1={obj1} , N2={obj1 , obj2} .....

3- And the main idea to solve the sub knapsack problem of the size Z <= S and considering the sub space of solution Ni we need 2 values:

· The max benefit that we can get from the knapsack Z considering the for the subset Ni-1

· The max benefit that we can get from the knapsack (Z-si) considering the for the subset Ni-1

Therefore, if the max benefit from the knapsack Z-si added to the value pi is higher than knapsack Z for the solution space compose from the subset Ni-1, then the solution would be to add the item i to the set of object selection in the knapsack Z-si. If not the solution for the intermediate knapsack Z / Ni would be the solution knapsack Z / Ni-1.


No comments: