# Dynamic programming

This notebook is based on the tutorial on Dynamic programming on this webpage (in Russian): https://bestprogrammer.ru/izuchenie/uchebnik-po-dinamicheskomu-programmirovaniyu-sozdanie-effektivnyh-programm-na-python

## Imports


```python
import time
import matplotlib.pyplot as plt
```

## Recursive algorithm for Fibonacci numbers


```python
%%timeit

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
    
fib(10)
```

    17.5 µs ± 228 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)


## Recursive algorithm with memoization for Fibonacci numbers


```python
%%timeit

cache = {}

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    elif n in cache:
        return cache[n]
    else:
        cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
    
fib(10)
```

    2.95 µs ± 27.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)


We can see that with memoization, the runtime decreases from 18 to 3 microseconds, that is, we get a six-fold improvement.

## Knapsack problem

Based on the description from https://en.wikipedia.org/wiki/Knapsack_problem as the original statement is incomprehensible.

We consider the problem of choosing some items from the given $n$ items such that the total value of these items is maximized but the total weight of these items does not exceed a given maximum capacity. This is called **0-1 knapsack problem** because we either take an item (1) or do not (0); we are not allowed to take fractions of the items.

Let's denote by $x_i$ if we take the $ith$ item or not: $x_i \in \{0, 1\}$. The value and the weight of the $i$th item are $v_i$ and $w_i$, respectively. The maximum allowed capacity is $M$.

Then, mathematically we solve the following problem:
$$
\begin{align}
\text{maximize}   & \sum_{i=1}^n x_i v_i \\
\text{subject to} & \sum_{i=1}^n x_i w_i \leq M,
\end{align}
$$
where $x_i \in \{0, 1\}$.

The following implementation and test problem follows https://en.wikipedia.org/wiki/Knapsack_problem


```python
def solve_knapsack_problem(v, w, M):
    """Solve knapsack problem with values `v`, weights `w`, and capacity `M`."""
    n = len(v)
    assert len(v) == len(w)
    
    cache = {}
    
    for i in (range(0, n)):
        cache[i, 0] = 0
    for j in (range(0, M+1)):
        cache[0, j] = 0
    
    for i in range(1, n):
        for j in range(0, M+1):
            if w[i] > j:
                cache[i, j] = cache[i-1, j]
            else:
                cache[i, j] = max(
                    cache[i-1, j],
                    cache[i-1, j-w[i]] + v[i]
                )
                
    return cache[n-1, M]
```


```python
v = [5, 4, 3, 2]
w = [4, 3, 2, 1]
M = 6

solve_knapsack_problem(v, w, M)
```




    9



## Coin change problem


```python

```

05692ceb14e8ab0aae66d68346872b0900ebcf5d
ipynb
Jupyter Notebook
2021-12-18-dynamic-programming.ipynb
dmitry-kabanov/datascience
487d7b8609320d7d207b030e5ba1b538d5bd1394
MIT
2021-12-18-dynamic-programming.ipynb
dmitry-kabanov/datascience
487d7b8609320d7d207b030e5ba1b538d5bd1394
MIT
2021-12-18-dynamic-programming.ipynb
dmitry-kabanov/datascience
487d7b8609320d7d207b030e5ba1b538d5bd1394
MIT
Qwen/Qwen-72B
1. YES
2. YES