Function MF_knapsack

dynamic_programming/knapsack.py:4–17

This code involves the concept of memory functions. Here we solve the subproblems which are needed unlike the below example F is a 2D array with -1s filled up

(i,wt,val,j)

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
"""
def MF_knapsack(i,wt,val,j):
    '''
    This code involves the concept of memory functions. Here we solve the subproblems which are needed
    unlike the below example
    F is a 2D array with -1s filled up
    '''
    global F  # a global dp table for knapsack
    if F[i][j] < 0:
        if j < wt[i - 1]:
            val = MF_knapsack(i - 1,wt,val,j)
        else:
            val = max(MF_knapsack(i - 1,wt,val,j),MF_knapsack(i - 1,wt,val,j - wt[i - 1]) + val[i - 1])
        F[i][j] = val
    return F[i][j]

def knapsack(W, wt, val, n):
    dp = [[0 for i in range(W+1)]for j in range(n+1)]