Modified O(km + kn) 0-1 knapsack java dp solution beating 99%


  • 0
    C

    The key idea that makes difference from their 3-d DP is that, when m and n allow, the solution has either averagely least number of 0s in each string or averagely least number of 1s in each string. It can be both, but it can't be neither.

    I start analyzing the problem by thinking it greedy. If I want as many strings formed as possible, I would want fewer 0s and 1s in the formed strings.

    Suppose we don't have the limit for number of 1s, if I sort the given array of strings by number of 0s in them, I would want to make use of as many smallest elements in this array as long as the sum of 0s is no more than m, and I can find these elements by greedy method.

    Now I set a limit for number of 1s, if the total number of 1s in previous elements I found doesn't exceed this limit, it means the number of these elements has to be the solution to this problem. However, if the limit is exceeded, my idea is to optionally remove some elements we found, and replace them by elements from the rest of the sorted array if possible. This is where I come to 0-1 knapsack.

    Limit for number of 1s is considered as weight, and number of strings formed is considered as value. We need another array int[][] w to keep track of the 0s, w[i][j] means the number of 0s used corresponding to the dp[i][j] value.

    Finally, we need to repeat what we did from the perspective of 1s, and set number of 0s as limit, the solution is the max of solution given by 0s and solution given by 1s.

    Here's my code.

    public int findMaxForm(String[] strs, int m, int n) {
            int[][] count = new int[strs.length][2];
            
            for(int i = 0; i < strs.length; i++) {
                for(char c : strs[i].toCharArray()) {
                    if(c == '0') count[i][0]++;
                    else count[i][1]++;
                }
            }
            
            return Math.max(findMaxFormBy(0, m, n, count), findMaxFormBy(1, n, m, count));
        }
        
        private int findMaxFormBy(int x, int m, int n, int[][] count) {// x is either 0 or 1.
            
            int[] numX = new int[count.length+1]; // digit of interest
            int[] numY = new int[count.length+1]; // the other digit as limit
            
            Arrays.sort(count, new Comparator<int[]>() {
               public int compare(int[] a, int[] b) {
                   return a[x] - b[x];
               } 
            });
            
            for(int i = 0; i < count.length; i++){
                numX[i+1] = count[i][x];
                numY[i+1] = count[i][1-x];
            }
            
            int[][] dp = new int[count.length+1][n+1]; // number of strings could be formed
            int[][] w = new int[count.length+1][n+1]; // corresponding number of digits of interest
            
            for(int i = 1; i <= count.length; i++) {
                for(int j = 1; j <= n; j++) {
                    if(numY[i] <= j && dp[i-1][j] < dp[i-1][j-numY[i]] + 1 
                                         && numX[i] + w[i-1][j-numY[i]] <= m) {
                        dp[i][j] = dp[i-1][j-numY[i]] + 1;
                        w[i][j] = numX[i] + w[i-1][j-numY[i]];
                    }else{
                        dp[i][j] = dp[i-1][j];
                        w[i][j] = w[i-1][j];
                    }
                }
            }
            
            return dp[count.length][n]; 
        }
    

Log in to reply
 

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