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

**and**

*i***the size of the object**

*s*_{i}

*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_{1}/s_{1} >= p_{2}/s_{2} >= p_{3}/s_{3}** .......

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_{1}={obj1}** ,

**.....**

*N*_{2}={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

**we need 2 values:**

*N*_{i}· 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*

*is higher than knapsack*

**p**_{i}**for the solution space compose from the subset**

*Z***, then the solution would be to add the item**

*N*_{i-1}

*i**to the set of object selection in the knapsack*

**. If not the solution for the intermediate knapsack**

*Z-s*_{i}**Z / N**would be the solution knapsack

_{i}

*Z / N*_{i-1.}_{}

_{......}

## No comments:

Post a Comment