0-1 knapsack in python


  • 16

    This question is very similar to a 0-1 knapsack, the transition function is

    dp(k, x, y) = max(dp(k-1, x-z, y-o) + 1, dp(k-1, x, y))   (z is zeroes in strs[k], o is ones in strs[k])
    

    dp(k, x, y) is the maximum strs we can include when we have x zeros, y ones and only the first k strs are considered.

    dp(len(strs), M, N) is the answer we are looking for

    I first implemented a dfs + memoization, which gets MLE, so I created a bottom up style dp.
    With bottom up, we can use something called "rolling array" to optimize space complexity from O(KMN) to O(MN)

    class Solution(object):
        def findMaxForm(self, strs, m, n):
            
            dp = [[0] * (n+1) for _ in range(m+1)]
            
            def count(s):
                return sum(1 for c in s if c == '0'), sum(1 for c in s if c == '1')
            
            for z, o in [count(s) for s in strs]:
                for x in range(m, -1, -1):
                    for y in range(n, -1, -1):
                        if x >= z and y >= o:
                            dp[x][y] = max(1 + dp[x-z][y-o], dp[x][y])
                            
            return dp[m][n]
    

  • 0
    H

    Could you please explain whats the idea behind the rolling array and how you converted the inductive step to:
    dp[x][y] = max(1 + dp[x-z][y-o], dp[x][y])


  • 5

    @Harold-Finch Consider a typical 0-1 knapsack problem, dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]), where dp[i][c] is the max value we can get considering the first i items being put into a knapsack with capacity c, w[i] is the weight of ith item, and v[i] is value. A naive implementation of this is to use a 2D array dp. However, based on the observation that the value of dp[i][c] is always based on values one row above (dp[i-1]) and to its left, we don't need to keep all previous computed results (dp[i-2] and above). If we replace the 2D array, dp, with 1D array, say ra, right before starting the ith iteration, ra contains values from i-1th iteration. If we iterate ra from right to left, and when we are trying to compute ra[j], we can be sure that all elements to the left of ra[j], including ra[j], are from previous iteration, which are the values we want use. This technique is sometimes referred to as "rolling array". And this problem is a 2D extension of a 1D 0-1 knapsack, and we use "rolling array" to reduce dp from 3D to 2D.


  • 0
    H

    @mlaw0 Thanks a lot!


  • 0
    L

    @mlaw0 Great solution. One thing I couldn't understand, for the x and y loop, why cant we start from lower bound, rather than upper bound ( i.e- m and n) ?


  • 5

    @logicless

    dp(k, x, y) = max(dp(k-1, x-z, y-o) + 1, dp(k-1, x, y))
    This is the orignal state transition funciton. The implementation optimize the space complexity. It used only two dimensional array dp(x, y). Think like this, when at k iteration(the outer loop), we want to keep dp(x-z, y-o) and dp(x,y) are the state at k-1. Because of this dp(x, y) is depending on something in front of it dp(x-z, y-o), that's why we want to loop x and y from m and n, otherwise at k iteration, dp(x-z, y-o)is already updated, are the state at k not k-1.


  • 1
    R

    not sure why but the same code doesn't get accepted on Python3, but does get accepted on Python2


  • 0
    G

    @rohithiitj Same here. OJ seems not working properly for Python solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.