Java 0/1 knapsack solution practice


  • 0
    D
    public class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            if (strs == null || strs.length == 0) {
                return 0;
            }
            Record[] records = new Record[strs.length];
            for (int i = 0; i < strs.length; i++) {
                records[i] = getRecord(strs[i]);
            }
            Integer[][][] dp = new Integer[strs.length][m + 1][n + 1];
            return get(dp, strs.length - 1, m, n, records);
        }
    
        private int get(Integer[][][] dp, int i, int j, int k, Record[] records) {
            if (dp[i][j][k] != null) {
                return dp[i][j][k];
            }
            int candidate1 = i >= 1 ? get(dp, i - 1, j, k, records) : 0;
            int candidate2 = (records[i].zeros <= j && records[i].ones <= k) ?
                    (1 + (i >= 1 ? get(dp, i - 1, j - records[i].zeros, k - records[i].ones, records) : 0)) : 0;
            return dp[i][j][k] = Math.max(candidate1, candidate2);
        }
    
        private Record getRecord(String str) {
            if (str == null || str.length() == 0) {
                return new Record(0, 0);
            }
            int zeros = 0;
            int ones = 0;
            for (int i = 0; i < str.length(); i++) {
                zeros += str.charAt(i) == '0' ? 1 : 0;
                ones += str.charAt(i) == '1' ? 1 : 0;
            }
            return new Record(zeros, ones);
        }
    
        private static class Record {
            int zeros;
            int ones;
    
            Record(int zeros, int ones) {
                this.zeros = zeros;
                this.ones = ones;
            }
        }
    }
    

Log in to reply
 

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