Problem statement

https://binarysearch.com/problems/0-1-Knapsack/

Solution

Classical knapsack problem, which can be solved with dp.

Complexity

It is O(nm) for time and O(m) for space.

Code

class Solution:
    def solve(self, wt, val, m):
        dp = [0] * (m + 1)
        for i in range(1, len(wt) + 1):
            cp = dp[:]
            q, t = wt[i - 1], val[i - 1]
            for w in range(wt[i - 1], m + 1):
                dp[w] = max(dp[w], cp[w - q] + t)
        return dp[-1]