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 v_i be the value of the object i and s_i 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).

P₁/s₁ >= p₂/s₂ >= p₃/s₃ .......

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 N₁={obj1} , N₂={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 N_i we need 2 values:

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

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

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

_......