## DEV Community is a community of 660,470 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Knapsack Variation

Santhosh Balasa
Passionate Senior Full Stack Developer around 10+ yrs of IT experience.

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)))
``````