There are three ways to implement a Knapsack Algorithm:
- Knapsack Recursive (Basic)
- Knapsack Memoization (Cached)
- 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)))
Discussion (0)