#!/usr/bin/env python
# coding: utf-8

# ![alt text](https://github.com/callysto/callysto-sample-notebooks/blob/master/notebooks/images/Callysto_Notebook-Banner_Top_06.06.18.jpg?raw=true)

# # Introduction to Dynamic Programming
# 
# ## We solve a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.
# 
# ### The key idea is called "memoization" (not "memorization") and the details appear in this YouTube video

# In[1]:


from IPython.display import YouTubeVideo
YouTubeVideo('e0CAbRVYAWg')


# In[2]:


## Let's create a function for the famous Fibonacci sequence, using the "naive recursive" approach.
## You'll notice how slow this process is.

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

fib(30),fib(31),fib(32)


# In[3]:


## Now here is how to code Fibonacci, using Dynamic Programming.  Look how fast this program runs!

def fib(n): 
    myset = [0]*(n+1) 
    myset[1]=1
    myset[2]=1
    for k in range(3,n+1):
        myset[k]=myset[k-1]+myset[k-2]
    return myset[n]

fib(30),fib(31),fib(32),fib(100)



# In[4]:


## Why does this code work?  Let's add a "print" statement so we see exactly what is going on in each step.
## Can you figure it out?  And why is this better than our first "naive recursion" approach?

def fib(n):
    myset = [0]*(n+1) 
    print("Step 0 ->", myset)
    myset[1]=1
    print("Step 1 ->", myset)
    myset[2]=1
    print("Step 2 ->", myset)
    for k in range(3,n+1):
        myset[k]=myset[k-1]+myset[k-2]
        print("Step" , k , "->", myset)
    return myset[n]

fib(8)


# # The Knapsack Problem
# 
# ## Let's solve one of the hardest problems in Computer Science with dynamic programming.

# In[5]:


from IPython.display import YouTubeVideo
YouTubeVideo('xOlhR_2QCXY')


# In[7]:


## Suppose there are five items, using the example from the above video.
## Let's assume that the 0th item has weight 0 and value 0, to make our indexing more intuitive.

from collections import namedtuple
Item = namedtuple("Item", ['index', 'weight', 'value'])

item_count = 5
capacity = 10
input_data = [[0,0],[1,5],[2,3],[4,5],[2,3],[5,2]]

items = []
for i in range(0, item_count+1):
    line = input_data[i]
    items.append(Item(i, int(line[0]), int(line[1])))
    
items


# In[8]:


## Set up our matrix V, which will be 6 rows and 11 columns.
## The row indices will range from i=0..5 and the column indices from j=0..10 
## V[i,j] equals the maximum value from the first i items, with total weight at most j.

V = [[0]*(capacity+1) for x in range(0,item_count+1)]
V


# In[9]:


## Complete the first step of our algorithm
for w in range(items[1].weight, capacity+1): 
    V[1][w]=items[1].value
V


# In[10]:


## Complete the remaining steps of our algorithm, one object at a time.
for i in range(1,len(items)):
    x=items[i]
    for w in range(0,capacity+1):
        if x.weight>w: V[i][w]=V[i-1][w]
        else: V[i][w]=max(V[i-1][w],x.value+V[i-1][w-x.weight])
V


# In[11]:


optimal_value=V[item_count][capacity]
optimal_value


# In[12]:


## Now we know that the optimal solution has value=16.  Let's figure out which items were chosen.
## Can you figure out how this code works?

chosen_items=[]
i=item_count
w=capacity
while i>=0 and w>=0:
    if V[i][w]!=V[i-1][w]: 
        if items[i].weight>0: chosen_items.append(items[i])
        w=w-items[i].weight
    i=i-1
chosen_items


# In[13]:


## Now let's try a super-hard example!

item_count = 19
capacity = 31181

input_data=[[0,0],[1945, 4990],[321, 1142],[2945, 7390],[4136, 10372],[1107, 3114],[1022, 2744],[1101, 3102],[2890, 7280],
[962, 2624],[1060, 3020],[805, 2310],[689, 2078],[1513, 3926],[3878, 9656],[13504, 32708],[1865, 4830],[667, 2034],[1833, 4766],
[16553, 40006]]

items = []
for i in range(0, item_count+1):
    line = input_data[i]
    items.append(Item(i, int(line[0]), int(line[1])))
    
items


# In[15]:


totalw=0
totalv=0
V = [[0]*(capacity+1) for x in range(0,item_count+1)]
for w in range(items[1].weight, capacity+1): 
    V[1][w]=items[1].value
for i in range(1,len(items)):
    x=items[i]
    for w in range(0,capacity+1):
        if x.weight>w: V[i][w]=V[i-1][w]
        else: V[i][w]=max(V[i-1][w],x.value+V[i-1][w-x.weight])
optimal_value=V[item_count][capacity]
chosen_items=[]
i=item_count
w=capacity
while i>=0 and w>=0:
    if V[i][w]!=V[i-1][w]: 
        if items[i].weight>0: 
            chosen_items.append(items[i])
            totalw=items[i].weight+totalw
            totalv=items[i].value+totalv
        w=w-items[i].weight
    i=i-1
print("Optimal Value is", optimal_value, "and our Total Capacity is", capacity)
print("And below are our chosen items with total weight", totalw, "and total value", totalv)
chosen_items


# ![alt text](https://github.com/callysto/callysto-sample-notebooks/blob/master/notebooks/images/Callysto_Notebook-Banners_Bottom_06.06.18.jpg?raw=true)