Knapsack Algorithm

# 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() 

// 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()) ); } 

Knapsack Recursive -> 7 Knapsack Memoization -> 7 Knapsack TopDown -> 7