Knapsack Algorithm

There are three ways to implement a Knapsack Algorithm:

1. Knapsack Recursive (Basic)
2. Knapsack Memoization (Cached)
3. Knapsack TopDown (Optimized)

# Knapsack Problem Recursive

def knapsack(w, v, W, n):
    if n == 0 or W == 0:
        return 0
    if w[n-1] <= W:
        return max(
            v[n-1] + knapsack(w, v, W-w[n-1], n-1), 
            knapsack(w, v, W, n-1)
        )
    else:
        return knapsack(w, v, W, n-1)

# Knapsack Problem Memoization

def knapsack_memoization(w, v, W, n):
    t = [[-1 for _ in range(W+1)] for _ in range(n+1)]  # Matrix n x W
    if n == 0 or W == 0:
        return 0
    if t[n][W] != -1:
        return t[n][W]
    if w[n-1] <= W:
        t[n][W] = max(
            v[n-1] + knapsack_memoization(w, v, W-w[n-1], n-1),
            knapsack_memoization(w, v, W, n-1)
        )
    else:
        t[n][W] = knapsack_memoization(w, v, W, n-1)
    return t[n][W]

# Knapsack Problem Top Down

def knapsack_top_down(w, v, W, n):
    t = [[-1 for _ in range(W+1)] for _ in range(n+1)] # Matrix n x W
    for i in range(n+1):
        for j in range(W+1):
            if i == 0 or W == 0:
                t[i][j] = 0
    for i in range(1, n+1):
        for j in range(1, W+1):
            if w[i-1] <= j:
                t[i][j] = max(v[i-1] + t[i-1][j-w[i-1]], t[i-1][j])
            else:
                t[i][j] = t[i-1][j]
    return t[n][W]

# Input
w = [2, 3, 4, 5] # Weights
v = [3, 4, 5, 6] # Values 
W = 5 # Max Knapsack Capacity

# Output
print("Knapsack Recursive -> ", knapsack(w, v, W, len(w)))
print("Knapsack Memoization -> ", knapsack_memoization(w, v, W, len(w)))
print("Knapsack TopDown -> ", knapsack_top_down(w, v, W, len(w)))