0-1 knapsack bottom-up java solution


  • 0
    C
    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m + 1][n + 1];
            for (String str : strs) {
                strInformation strInfo = new strInformation(str);
                for (int currM = m; currM >= strInfo.zeroNum; currM--) {
                    for (int currN = n; currN >= strInfo.oneNum; currN--) {
                        dp[currM][currN] = Math.max(dp[currM][currN], 
                                                    dp[currM - strInfo.zeroNum][currN - strInfo.oneNum] + 1);
                    }
                }
            }
            return dp[m][n];
        }
    }
    
    class strInformation {
        int zeroNum;
        int oneNum;
        String str;
        
        strInformation(String str) {
            this.str = str;
            int zero = 0;
            int one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') { zero++;}
                else { one++; }
            }
            this.zeroNum = zero;
            this.oneNum = one;
        }
    }
    

    0_1514066078274_544e2a48-f1df-4b61-bb92-96ec5f9687fa-image.png

    The formula is (zero is the 0s that this str has, one is the 1s that this str has)

    if (m < zero || n < one) { T[i][j] = T[i - 1][j] }
    
    if (m > zero && n > zero) 
    { T[i][j] = Math.max(T[i - 1][j], 1 + T[i][j']) } (j' is value at T[i][m - zero, n - one])
    
    

Log in to reply
 

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