0-1 knapsack in python

• 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]
``````

• 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])`

• @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 `i`th 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 `i`th iteration, `ra` contains values from `i-1`th 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.

• @mlaw0 Thanks a lot!

• @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`) ?

• @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`.

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

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

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