创造新世界
众所周知计算机代码底层计算都是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
代码如下:
import java.util.Scanner;
public class Main {
static int[] n = new int[21];
static int[] m = new int[21];
static int X;
static int N;
static int M;
static int[][] dp = new int[501][501];
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
X = in.nextInt();
N = in.nextInt();
M = in.nextInt();
for ( int i = 1 ; i <= X ; i++){
String str = in.next();
char[] ch = str.toCharArray();
for ( int j = 0 ; j < ch.length ; j++){
if ( ch[j] == '0'){
n[i]++;
}else{
m[i]++;
}
}
}
//二维动态规划，背包问题
for ( int i = 1 ; i <= X ; i++){
for ( int j = N ; j >= n[i] ; j--){
for ( int k = M ; k >= m[i] ; k--){
dp[j][k] = Math.max(dp[j][k], dp[j-n[i]][k-m[i]]+1);
}
}
}
System.out.print(dp[N][M]);
in.close();
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读