Problem statement

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

Solution 1

Use classical 0-1 knapsack, but add elements x, 2x, 4x and so on. In this way it is possible to reconstruct answer in the end.

Complexity

It is O(mn * log m) for time and O(n log m + m) for space.

Code

class Solution:
    def solve(self, wt, val, m):
        wt2, val2 = [], []
        for w, v in zip(wt, val):
            while w <= m:
                wt2 += [w]
                val2 += [v]
                w, v = 2*w, 2*v

        dp = [0] * (m + 1)
        for i in range(1, len(wt2) + 1):
            cp = dp[:]
            q, t = wt2[i - 1], val2[i - 1]
            for w in range(wt2[i - 1], m + 1):
                dp[w] = max(dp[w], cp[w - q] + t)
        return dp[-1]

Solution 2

Actually, there is O(mn) time solution as well. We do not need to keep cp copy here, but work directy with dp. However I do not know how to reconstruct answer in this way.

Complexity

It is O(mn) 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):
            q, t = wt[i - 1], val[i - 1]
            for w in range(wt[i - 1], m + 1):
                dp[w] = max(dp[w], dp[w - q] + t)
        return dp[-1]