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( ¤t_value, &profits, saving, current_value.len(), &mut t ) ); } 
Top comments (0)