multi-dimensional cost 0-1 knapsack problem with two backpack sizes

user_10543735 0
Viewed 608

I was going through the solutions to this problem found on leetcode.

The problem states:

Given an array, strs, with strings consisting of only 0s and 1s. Also two integers m and n.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3

Output: 4

Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0".

The algorithm used to solve the problem is below:

def findMaxForm(strs, m, n):

    dp = [[0] * (n + 1) for _ in range(m +1)]
    
    for s in strs:
        
        zeros, ones = s.count('0'), s.count('1')
        
        for i in range(m, zeros - 1, -1):
            
            for j in range(n, ones -1, - 1):
                
                # dp[i][j] indicates it has i zeros ans j ones,
                # can this string be formed with those ?
                
                dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j])
                
            # print(dp)
            
    return dp[-1][-1]

the confusing part of the problem is the dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j]). I am not sure what is going on here. Why do we minus i from zeros and j from ones?

I also found a diagram that explains how the dp table should look for ever element in the array.

My Questions:

  • what does the first table represent? The x and y axis? Why are there so many 1's. I think if i understand this part, something might click. I would appreciate if someone walks through the diagram
  • why does this way give us the maximum number of 0's and 1's that can be formed? i think i am stil confused about this part dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j]).
  • Also the solution is described as a "3d-DP optimized to 2D space: dp[j][k]: i dimension is optimized to be used in-place." What does that mean?

01

knapsack-problem dynamic-programming data-structures algorithm python
1 Answers

When you encounter a string s, you basically have two options. It either belongs to the maximal solution, or it doesn't.

If you do, the size of the set is increased by one, but you have less ones and zeros left to use. If you don't use it, the size of the set remains unchanged, but so is the number if left ones and zeros.

The table dp represnts the maximal such set you can get until now for different number of ones and zeros "left". For example. dp[m][n] means the best value you can get so far with m zeros and n ones. Similarly, for dp[2][3] you can use 2 zeros and 3 ones for the rest of the strings.

Let's wrap it together:

For some given number of zeros (i) left to use, and some number of ones (j) left to use, and a string s:

  • 1 + dp[i - zeros][j - ones] means the maximal set if you decide to add s to the set (and you are left with less ones and zeros)
  • dp[i][j] means you are not taking this element, and moving on.

When you invoke max() on both values, you basically say: I want the better one out of these two options.

I hope this answers the first two questions, of why it is maximal and what the dp line means.

Also the solution is described as a "3d-DP optimized to 2D space: dp[j][k]: i dimension is optimized to be used in-place." What does that mean?

In here, you have 3d problem: the strings themselves, which you iterate over - but you don't have another dimension for the array. You optimize it to be inplace since you always only need the previous string, and never something "older" than it, saving you precious space.

user_5726700
Related