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