背包系列问题4——二维背包

参考资料：
1. 动态规划之背包问题系列
2. #### 一和零

    public int findMaxForm(String[] strs, int m, int n) {
        int numOfChoice = strs.length;

        // int[][][] dp = new int[numOfChoice+1][m+1][n+1];
        //
        // for (int i = 1; i <= numOfChoice; i++) {
        //     int w0 = (int)strs[i-1].chars().filter(x -> x == '0').count();
        //     int w1 = (int)strs[i-1].chars().filter(x -> x == '1').count();
        //
        //     for (int j = 0; j <= m; j++) {
        //         for (int k = 0; k <= n; k++) {
        //             int left0 = j - w0;
        //             int left1 = k - w1;
        //             if(left0 >= 0 && left1 >= 0) {
        //                 dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][left0][left1] + 1);
        //             }else{
        //                 dp[i][j][k] = dp[i - 1][j][k];
        //             }
        //         }
        //     }
        // }
        //
        // return dp[numOfChoice][m][n];

        int[][] dp = new int[m+1][n+1];

        for (int i = 1; i <= numOfChoice; i++) {
            int w0 = (int)strs[i-1].chars().filter(x -> x == '0').count();
            int w1 = (int)strs[i-1].chars().filter(x -> x == '1').count();

            for (int j = m; j >= 0; j--) {
                for (int k = n; k >= 0; k--) {
                    int left0 = j - w0;
                    int left1 = k - w1;
                    if(left0 >= 0 && left1 >= 0) {
                        dp[j][k] = Math.max(dp[j][k], dp[left0][left1] + 1);
                    }
                }
            }
        }

        return dp[m][n];
    }