众所周知计算机代码底层计算都是0和1的计算， 牛牛知道这点之后就想使用0和1创造一个新世界！ 牛牛现在手里有n个0和m个1，给出牛牛可以创造的x种物品， 每种物品都由一个01串表示。 牛牛想知道当前手中的0和1可以最多创造出多少种物品。 输入描述: 输入数据包括x+1行： 第一行包括三个整数x(2 ≤ x ≤ 20)，n(0 ≤ n ≤ 500)，m(0 ≤ m ≤ 500)，以空格分隔 接下来的x行，每行一个01串item[i]，表示第i个物品。每个物品的长度length(1 ≤ length ≤ 50) 输出描述: 输出一个整数，表示牛牛最多能创造多少种物品 输入例子: 3 3 1 1 00 100 输出例子: 2 *二维背包问题： *对于每件物品,当选择这件物品必须同时付出两种代价； *对于每种代价都有一个可付出的最大值（背包容量）。 *问怎样选择物品可以得到最大的价值。 *设第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为u和v。物品的价值为w[i]。 *状态转移方程：dp[i][u][v] = max(dp[i-1][u][v] , w[i] + dp[i-1][u-a[i]][v-b[i]]) *同样的进行空间压缩，我们可以得到二维数组的状态转移方程，如下： *dp[u][v] = max(dp[u-a[i]][v-b[i]]+w[i],dp[u][v]) *注：u、v在此均采用倒序！
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int x=sc.nextInt(); int n=sc.nextInt(); int m=sc.nextInt(); sc.nextLine(); int[] zero = new int[x]; int[] one = new int[x]; for(int i = 0; i < x; i++){ char[] temp = sc.nextLine().toCharArray(); int cnt = 0; for(int j = 0; j < temp.length; j++){ if(temp[j] == '0') cnt++; } zero[i] = cnt; one[i] = temp.length - cnt; } sc.close(); //物品有0和1两种代价，所以是二维背包 int dp[][] = new int[n+1][m+1]; //dp[i][j]表示有i个0，j个1时，能造出多少物品 for(int i = 0; i < x; i++){ //倒序遍历是因为每一次采用的状态是上一次的，若是正序就会把要用的状态覆盖成本次的 for(int j = n; j >= zero[i]; j--){ for(int k = m; k >= one[i]; k--){ dp[j][k]=Math.max(dp[j][k],dp[j-zero[i]][k-one[i]]+1); } } } System.out.println(dp[n][m]); } }