# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # 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

import time
import matplotlib.pyplot as plt


# ## Recursive algorithm for Fibonacci numbers

# +
# %%timeit

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

# ## Recursive algorithm with memoization for Fibonacci numbers

# +
# %%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)


# -

# 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

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]


# +
v = [5, 4, 3, 2]
w = [4, 3, 2, 1]
M = 6

solve_knapsack_problem(v, w, M)

# + [markdown] tags=[]
# ## Coin change problem
# -



StarcoderdataJupyterScriptsDedupFiltered