Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
911 B
4
Indexable
Never
def knapsack(saving, current_value, future_value):
    n = len(current_value)
    profits = [j - i for i, j in zip(current_value, future_value)]
    memo = [[-1 for _ in range(saving + 1)] for _ in range(n + 1)]

    def knapsack_helper(weights, profits, capacity, n):
        if n == 0 or capacity == 0:
            return 0
        if memo[n][capacity] != -1:
            return memo[n][capacity]
        if weights[n - 1] > capacity:
            memo[n][capacity] = knapsack_helper(weights, profits, capacity, n - 1)
        else:
            include_item = profits[n - 1] + knapsack_helper(weights, profits, capacity - weights[n - 1], n - 1)
            exclude_item = knapsack_helper(weights, profits, capacity, n - 1)
            memo[n][capacity] = max(include_item, exclude_item)
        
        return memo[n][capacity]

    return knapsack_helper(current_value, profits, saving, n)
Leave a Comment