knapsack.py

# Time Complexity: O(N*W).
#   As redundant calculations of states are avoided.
# Auxiliary Space: O(N*W).
#   The use of 2D array data structure

#### Example

# 4 items
# football, W:5, V:10
# vase,     W:10, V:40
# watch,    W:3, V:50
# TV:       W:12, V:75

# Put into a box C = 20
# W[5,10,3,12] and V[10,40,50,75]

# Call function recursively until either C or n == 0

# There may be overlapping issues 
# which does not help with performance, especially since this is recursive process.

# So we will represent processes done in a 2D table and refer to it before peforming
# a process to check if we have not done it before

def knapSack(capacity: int, weight: list, value: list, n: int) -> int:
    if capacity == 0 or n == 0: #validate
        return 0

    if table[n][capacity] != -1: #if there is already a value in table, skip
        return table[n][capacity] 

    if weight[n-1] <= capacity:        
        table[n][capacity] = max(value[n-1] + knapSack(capacity-weight[n-1], weight, value , n-1), knapSack(capacity, weight, value, n-1))

        return table[n][capacity]
    
    elif weight[n-1] > capacity:
        table[n][capacity] = knapSack(capacity,weight,value,n-1) #remove item

        return table[n][capacity]

if __name__ == "__main__":
    value = [10,40,50,75]
    weight = [3,5,10,15]
    capacity = 20
    n = len(value) #number of items

    table = [[-1 for i in range(capacity + 1)] for j in range(n + 1)] #Create 2D array

    output = knapSack(capacity,weight,value,n)

    print(output)