Problem statement

https://binarysearch.com/problems/Multi-Knapsack/

Solution

Classical dp problem, where state is (taken weigth, taken count, index). On each step we can either take or not take new item. We can do it either with recursion or we can do it layer by layer, from index generate all element with index + 1.

Complexity

It is O(cap * n^2) for time and O(cap * n) for space.

Code

class Solution:
    def solve(self, W, values, cap, count):
        n = len(W)
        dp = {(0, 0): 0}
        for i in range(n):
            dp2 = Counter()
            for w, t in dp:
                dp2[w, t] = max(dp2[w, t], dp[w, t])
                if w + W[i] <= cap and t + 1 <= count:
                    dp2[w + W[i], t + 1] = max(dp2[w + W[i], t + 1], dp[w, t] + values[i])
            dp = dp2

        return max(dp.values())