## 1 dimension Knapsack problem

Find a way to pack items

defined by their respective value and weight

in a sack of a given capacity so that the total value is as large as possible.

### Decision variables

### Constraints

### Objective function

## Recursive naive top-down

assume we know how to compute the best solution for for all ,

we want to solve .

if

otherwise

so we can write a recursive top-down solver:

```
int O(int k,int j) {
if (j == 0)
return 0;
else if (wj <= k)
return max(O(k,j-1),vj + O(k-wj,j-1)); // unnecessary exponential groth
else
return O(k,j-1)
}
```

the unnecessary exponential groth computes many times the same

to avoid this we are going to build our solution from the bottom

## Dynamic Programming

- it is a divide and conquer
- bottom up computation technique

maximize

subject to

domain

k \ i | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | 0 |

1 | 0 | 0 | 0 | 0 | 0 |

2 | 0 | 16 | 16 | 16 | 16 |

3 | 0 | 16 | 19 | 19 | 19 |

4 | 0 | 16 | 19 | 23 | 23 |

5 | 0 | 16 | 35 | 35 | 35 |

6 | 0 | 16 | 35 | 39 | 39 |

7 | 0 | 16 | 35 | 42 | 44 |

this table is easily built from top to bottom, left to right.

```
for i (1..4) {
for k (0..7) {
if ((k >= wi) && (([i-1, (k-Wi)] + vi)> [i-1, k]))
[i, k] = ([i-1, (k-Wi)] + vi);
else
[i, k] = [i-1, k];
}
}
```

when done the best value can be read in the bottom right cell.

to find the items, we trace back the algorithme from this bottom right cell.

If it’s value is the same the the cell on the right, the item index *i* is not taken, move to the cell on the right,

otherwise the intem *i* is taken, move right and up .

For this particular case, the tracing back goes [ *44* , *16* , *16* , *16* , *0* ] and the items are **1** and **4**.

This is a pseudo-polynomyal algorithm, very fast for small values of **K**, otherwise exponential.

## Branch and Bound

- branching : split the problem into subproblems
- bounding : use optimistic estimation
- if we are
**maximizing**an objective function we take the upper bound of this function - if we are
**minimizing**an objective function we take the lower bound of this function

- if we are

### Branch-Bound

#### Relax the capacity constraint

optimistc value is

#### Linear relaxation

relax the integrality requirement

- sort the item by the ratio
- the optimistic value becomes:
- take the ordered items one by one untill the next one weights more than the capacity
- fill the capacity with of fraction of the next item

### Depth-First Branch-Bound

- prunes when a node estimation is worst than the best found solution
- memory efficient

### Depth-First Branch-Bound

- select the node with the best evaluation
- prunes whem all the nodes are worse than a found solution
- could be realy not memory efficient

Back to Wisdom entry