## DEV Community is a community of 660,470 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Knapsack Algorithm Santhosh Balasa
Passionate Senior Full Stack Developer around 10+ yrs of IT experience.

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)))
``````