Knapsack Algorithm

There are three ways to implement a Knapsack Algorithm:

1. Knapsack Recursive (Basic)
2. Knapsack Memoization (Cached)
3. 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