创造新世界

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

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法提高 金陵十三钗

    金陵十三钗   本题难度:难   本题占分比例:5% 问题描述   在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本...

    AI那点小事
  • 历届试题 最大子阵

    问题描述   给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。

    AI那点小事
  • 寻找大富翁

    题目描述 浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁. 输入描述: 输入包含多组测试用例. 每个用例首先包含2个...

    AI那点小事
  • #627 DIV3 题解

    在找到两个数相等之后,由于是子序列可以不连续,在两个数之间随便找一个数即可,所以条件就是且$i+1

    ACM算法日常
  • Java工具集-验证码工具类

    cwl_java
  • Hebuter Daily Training 201810

    有三个人Y,W,D.每个人都很想去一个地方.但是不好请假.所以能去一个 地方就很好了.Y想出来一个方法.每个人掷骰子.点数最多的赢.就可以去 他想去的地方.Y,...

    xiaohejun
  • 对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

    本质上Dijkstra是一种贪心,满足局部最优,每次找的是离起点最近的(保证了这个点的距离就是最短路),如果有负边权,当前找到的就不一定是最近的了。

    ACM算法日常
  • cf547D. Mike and Fish(欧拉回路)

    attack
  • POJ 3264 Balanced Lineup (RMQ模板题)

    用户2965768
  • 2016计蒜之道复赛 百度地图的实时路况(Floyd 分治)

    首先一个结论:floyd算法的正确性与最外层\(k\)的顺序无关(只要保证是排列即可)

    attack

扫码关注云+社区

领取腾讯云代金券