[Summary] Knapsack problems

变形的背包问题是DP中的一类典型题。例如[LC 474]. Ones and Zeroes. Given the restriction that m 0s and n 1s are available, and a string array like [“01”, “0001”, “1100010”,…], calculate the max number of strings that you can represent under the restriction. 对每个string,只有选择或不选择两个可能,是0/1背包问题。如果只有0个数的限制,或只有1个数的限制,greedy就可以做。如果每个string可以拆分,就像0/1背包问题中每个item可以拆分一样,那也可以用greedy做。但这个问题,只能用dp做。

  • 需要keep track的变量:1的个数和0的个数。所以存(m+1)*(n+1) matrix, dp[i][j]=no. of string when i 0s and j 1s are allowed
  • 需要update的公式:dp[i][j] = max(dp[i][j], dp[i-count0][j-count1])
    不take当前string take当前string
  • 循环是倒序的,见code。采用正序还是倒序,糊涂的时候用一个例子手动填写dp table试试。
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (String str : strs) {
            int[] count = binCount(str);
            if (count[0] > m || count[1] > n) continue;
            for (int i = m; i >= count[0]; i--) { // 倒序
                for (int j = n; j >= count[1]; j--) { // 倒序
                    dp[i][j] = Math.max(dp[i][j], dp[i-count[0]][j-count[1]] + 1);
                }
            }
        }
        
        return dp[m][n];
    }
    
    private int[] binCount(String s) {
        int[] count = new int[2];
        count[0] = s.replace("1","").length();
        count[1] = s.replace("0","").length();
        return count;
    }