knapsack_2d.py

class Solution:
    def knapsack(self, weights, profits, capacity):
        n = len(weights)
        dp = [[0] * (capacity + 1) for _ in range(n + 1)]
        dp[0][0] = 0

        for i in range(1, n + 1):
            for w in range(capacity + 1):
                if weights[i - 1] > w: # if item is too heavy, exclude it
                    dp[i][w] = dp[i - 1][w]
                else:
                    dp[i][w] = max(dp[i - 1][w], profits[i - 1] + dp[i - 1][w - weights[i - 1]])

        return dp[n][w]  # max value with all items and full capacity

if __name__ == "__main__":

    solution = Solution()

    weights = [1, 3, 4, 5]
    profits = [1, 4, 5, 7]
    capacity = 7

    result = solution.knapsack(weights, profits, capacity)
    assert result == 9
    print("Test Case Passed!")