字符构成最多的字符串
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: There are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001"
题目描述：
从字符串集合中尽可能多的选出字符串并保证0和1个数不超过给定值。
思路分析：
题目和0-1背包问题大同小异，区别是这里限制0和1个数，而0-1背包问题限制总重量。这里用dp[i] [j] [k]表示前i个字符串在0的个数不超过j，1的个数不超过k时最多能选取的字符串个数。统计第i个字符串中0和1 的个数分别为zero和one，如果取第i个字符串，则dp[i] [j] [k]=dp[i-1] [j-zero] [k-one]+1,如果不取第i个字符串，那么dp[i] [j] [k]=dp[i-1] [j] [k]，取两者的较大值作为dp[i] [j] [k]的值，由于dp[i] [j] [k]只和dp[i-1] [ * ] [ * ]有关，所以在实现的过程中可以将空间压缩为dp[j] [k]，只需在遍历时从后向前遍历即可。
代码：
public int findMaxForm(String[]strs,int m,int n){//多维0-1背包，有两个背包大小，0的数量和1的数量。
if(strs==null||strs.length==0)
return 0;
int [][]dp=new int[m+1][n+1];
for(String str:strs){
int one=0;
int zero=0;
for(char c:str.toCharArray()){
if(c=='0')
zero++;
else
one++;
}
for(int i=m;i>=zero;i--){
for(int j=n;j>=one;j--){
dp[i][j]=Math.max(dp[i][j],dp[i-zero][j-one]+1);
}
}
}
return dp[m][n];
}