Knapsack Variation

An investor has saved some money and wants to invest in the stock market. There are a number of stocks to choose from, and they want to buy at most 1 share in any company. The total invested cannot exceed the funds available. A friend who is a stock market expert has predicted the value of each stock after 1 year.
Determine the maximum profit that can be earned at the end of the year assuming the predictions come true.

In Python

def knapsack(w, v, W, n, t):
    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(w, v, W - w[n - 1], n - 1, t),
            knapsack(w, v, W, n - 1, t),
        )
    else:
        t[n][W] = knapsack(w, v, W, n - 1, t)
    return t[n][W]


def main():
    saving = 250
    current_value = [175, 133, 109, 201, 97]
    future_value = [200, 125, 128, 228, 133]

    # This is a 0/1 knapsack based algorithm
    t = [[-1 for i in range(1000)] for j in range(saving)]  # n x W matrix

    profits = [
        0 if j < j else j - i for i, j in zip(current_value, future_value)
    ]
    print(knapsack(current_value, profits, saving, len(current_value), t))


if __name__ == "__main__":
    main()

In Rust

use std::cmp;

fn knapsack(w: &Vec<i32>, v: &Vec<i32>, W: i32, n: usize, t: &mut Vec<Vec<i32>>) -> i32 {
    if n == 0 || W == 0 {
        return 0;
    }
    if t[n][W as usize] != -1 {
        return t[n][W as usize];
    }
    if w[n - 1] <= W {
        t[n][W as usize] = cmp::max(
            v[n - 1] + knapsack(w, v, W - w[n - 1], n - 1, t),
            knapsack(w, v, W, n - 1, t),
        );
    } else {
        t[n][W as usize] = knapsack(w, v, W, n - 1, t);
    }
    return t[n][W as usize];
}

fn main() {
    let saving: i32 = 250;
    let current_value = vec![175, 133, 109, 201, 97];
    let future_value = vec![200, 125, 128, 228, 133];
    let mut t = vec![vec![-1; 1000]; saving as usize + 1]; // (n+1) x W matrix

    let mut profits = Vec::new();
    for (i, j) in current_value.iter().zip(future_value.iter()) {
        profits.push(if j < i { 0 } else { j - i });
    }
    println!(
        "{}",
        knapsack(
            &current_value,
            &profits,
            saving,
            current_value.len(),
            &mut t
        )
    );
}