There are three ways to implement a Knapsack Algorithm:
- Knapsack Recursive (Basic)
- Knapsack Memoization (Cached)
- Knapsack TopDown (Optimized)
In Python
# 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]
def main():
# 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)))
if __name__ == "__main__":
main()
In Rust
// Knapsack Problem Recursive
fn knapsack(w: &Vec<usize>, v: &Vec<usize>, W: usize, n: usize) -> usize {
if n == 0 || W == 0 {
return 0;
}
if w[n - 1] <= W {
return std::cmp::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
fn knapsack_memoization(
w: &Vec<usize>,
v: &Vec<usize>,
W: usize,
n: usize,
t: &mut Vec<Vec<isize>>,
) -> isize {
if n == 0 || W == 0 {
return 0;
}
if t[n][W] != -1 {
return t[n][W];
}
if w[n - 1] <= W {
t[n][W] = std::cmp::max(
v[n - 1] as isize + knapsack_memoization(w, v, W - w[n - 1], n - 1, t), // convert v[n-1] to isize before adding
knapsack_memoization(w, v, W, n - 1, t),
);
} else {
t[n][W] = knapsack_memoization(w, v, W, n - 1, t);
}
return t[n][W];
}
// Knapsack Problem Top Down
fn knapsack_top_down(w: &Vec<usize>, v: &Vec<usize>, W: usize, n: usize) -> isize {
let mut t = vec![vec![-1; W + 1]; n + 1]; // Matrix n x W
for i in 0..n + 1 {
for j in 0..W + 1 {
if i == 0 || j == 0 {
t[i][j] = 0;
}
}
}
for i in 1..n + 1 {
for j in 1..W + 1 {
if w[i - 1] <= j {
t[i][j] = std::cmp::max(
v[i - 1] + t[i - 1][j - w[i - 1]] as usize,
t[i - 1][j] as usize,
) as isize;
} else {
t[i][j] = t[i - 1][j];
}
}
}
return t[n][W];
}
fn main() {
let w = vec![2, 3, 4, 5]; // Weights
let v = vec![3, 4, 5, 6]; // Values
let W = 5; // Max Knapsack Capacity
// Output
println!("Knapsack Recursive -> {}", knapsack(&w, &v, W, w.len()));
let mut t = vec![vec![-1; W + 1]; w.len() + 1];
println!(
"Knapsack Memoization -> {}",
knapsack_memoization(&w, &v, W, w.len(), &mut t)
);
println!(
"Knapsack TopDown -> {}",
knapsack_top_down(&w, &v, W, w.len())
);
}
Output
Knapsack Recursive -> 7
Knapsack Memoization -> 7
Knapsack TopDown -> 7
Top comments (0)