0-1 knapsack detailed explanation.


  • 29
    Z

    This problem is a typical 0-1 knapsack problem, we need to pick several strings in provided strings to get the maximum number of strings using limited number 0 and 1. We can create a three dimensional array, in which dp[i][j][k] means the maximum number of strings we can get from the first i argument strs using limited j number of '0's and k number of '1's.

    For dp[i][j][k], we can get it by fetching the current string i or discarding the current string, which would result in dp[i][j][k] = dp[i-1][j-numOfZero(strs[i])][i-numOfOnes(strs[i])] and dp[i][j][k] = dp[i-1][j][k]; We only need to treat the larger one in it as the largest number for dp[i][j][k].

    talking is cheap:

    public int findMaxForm(String[] strs, int m, int n) {
        int l = strs.length;
        int[][][] dp = new int[l+1][m+1][n+1];
        
        for (int i = 0; i < l+1; i++) {
            int[] nums = new int[]{0,0};
            if (i > 0) {
                nums = calculate(strs[i-1]);
            }
            for (int j = 0; j < m+1; j++) {
                for (int k = 0; k < n+1; k++) {
                    if (i == 0) {
                        dp[i][j][k] = 0;
                    } else if (j>=nums[0] && k>=nums[1]) {
                        dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-nums[0]][k-nums[1]]+1);
                    } else {
                        dp[i][j][k] = dp[i-1][j][k];
                    }
                }
            }
        }
        
        return dp[l][m][n];
    }
    
    private int[] calculate(String str) {
        int[] res = new int[2];
        Arrays.fill(res, 0);
        
        for (char ch : str.toCharArray()) {
            if (ch == '0') {
                res[0]++;
            } else if (ch == '1') {
                res[1]++;
            }
        }
        
        return res;
    }
    

    By the way, 0-1 knapsack we cannot decrease the time complexity, but we can decrease the space complexity from ijk to j*k

    public int findMaxForm(String[] strs, int m, int n) {
        int l = strs.length;
        int[][] dp = new int[m+1][n+1];
        
        for (int i = 0; i < m+1; i++) {
            Arrays.fill(dp[i], 0);
        }
        
        int[] nums = new int[]{0,0};
        for (String str : strs) {
            nums = calculate(str);
            for (int j = m; j >= nums[0]; j--) {
                for (int k = n; k >= nums[1]; k--) {
                    if (j>=nums[0] && k>=nums[1]) {
                        dp[j][k] = Math.max(dp[j][k], dp[j-nums[0]][k-nums[1]]+1);
                    } else {
                        dp[j][k] = dp[j][k];
                    }
                }
            }
        }
        
        return dp[m][n];
    }
    
    private int[] calculate(String str) {
        int[] res = new int[2];
        Arrays.fill(res, 0);
        
        for (char ch : str.toCharArray()) {
            if (ch == '0') {
                res[0]++;
            } else if (ch == '1') {
                res[1]++;
            }
        }
        
        return res;
    }
    

    If you know Chinese, http://love-oriented.com/pack/P01.html would help you a lot.


  • 2
    M

    Thanks, I think that's the best explanation.


  • 0
    L

    Best Solution! Man!


  • 3
    L

    Thanks! Inspired by your code,this is my code,more shorter.Beats 88.35% of java submissions.

    public static int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m + 1][n + 1];
            for(String str : strs){
                int one = 0;
                int zero = 0;
                for(char c : str.toCharArray()){
                    if(c == '1')
                        one++;
                    else
                        zero++;
                }
                for(int i = m; i >= zero; i--){
                    for(int j = n; j >= one; j--){
                        if(one <= j && zero <= i)
                            dp[i][j] = Math.max(dp[i][j],dp[i - zero][j - one] + 1);
                    }
                }
            }
            return dp[m][n];
        }
    

  • 0
    Y

    最近背包问题有点多啊
    ............


  • 0
    N

    c# solution

        public int FindMaxForm(string[] strs, int m, int n) {
            var dp = new int[m+1, n+1];
            foreach(var s in strs){
                var zero =0;
                var one =0;
                count(s, ref zero, ref one);
                
                for(var i=m;i>=zero;i--){
                    for(var j=n;j>=one;j--){
                        dp[i,j] = Math.Max(dp[i,j], dp[i-zero, j-one]+1);
                    }
                }
            }
            
            return dp[m, n];
        }
        
        public void count(string s, ref int zero, ref int one){
            foreach(var c in s){
                if(c=='1'){
                    one++;
                }
                else{
                    zero++;
                }
            }
        }
    

  • 0
    Z

    hi,
    can you explant
    why
    dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-nums[0]][k-nums[1]]+1);
    but not
    dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-nums[0]][k-nums[1]]+ "value of s" );

    thank you : )


  • 0

    @ZhuEason Upvoted because of your last line (and of course, your excellent solution):

    http://izquotes.com/quotes-pictures/quote-talk-is-cheap-show-me-the-code-linus-torvalds-273528.jpg


  • 0
    B

    @liboren silly doubt what does dp[i][j] denotes


  • 0
    L

    why i got TLE ... Did you got the TLE error?


  • 0

    @ZhuEason elegant! but you really don't need Arrays.fill. also, dp[j][k] = dp[j][k]; will never be reached.


  • 0
    Q

    Could you explain why can we decrease the space complexity in this knapsack problem particularly? Why should we decrease i and j counters instead of increase them in the loop in the second version?


  • 1
    V

    @qiuyingyue0516 If you increase them, you can use the current string multiple times but the question says we can use each string at most once. If you decrease them, you ensure that you use the current string at most once.

    Ex. ["1", "1"], m = 0, n = 2
    If you increase i and j, after the first iteration over the first "1" string, dp looks like:
    [
    [0,1,2]
    ]
    But this is wrong, dp[0][2] can't be 2 since we can only use the "1" string once, it should be 1.

    If you decrease i and j instead of increase, dp will look like:
    [
    [0,1,1]
    ]
    which is correct.


  • 0
    R

    Thank you for your explanation!


Log in to reply
 

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