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)