# Java 0/1 knapsack solution practice

• ``````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;
}
}
}
``````

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