创造新世界

众所周知计算机代码底层计算都是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

---

代码如下:

代码语言：javascript复制

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();
    }

}

计算机

0 人点赞