DEV Community

loading...
Cover image for Knapsack Variation

Knapsack Variation

Santhosh Balasa
Passionate Senior Full Stack Developer around 10+ yrs of IT experience.
・1 min read

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)))
Enter fullscreen mode Exit fullscreen mode

Discussion (0)