首页 > 试题广场 >

创造新世界

[编程题]创造新世界
  • 热度指数：1135 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
众所周知计算机代码底层计算都是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)


输出描述:
输出一个整数，表示牛牛最多能创造多少种物品
示例1

输入

3 3 1 1 00 100

输出

2
算法知识视频讲解
添加回答
YoHoooo头像 YoHoooo
最多创造出多少种物品。 
看成最多能创造多少个物品了。。。
发表于 2017-03-26 11:50:25 回复(0)
牛客511771125号头像 牛客511771125号 
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

int main()
{
	int x, n, m;
	cin >> x >> n >> m;
	vector<vector<int>> nmNeed(x, vector<int>(2,0));
	for (int i = 0; i < x; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); j++)
		{
			nmNeed[i][str[j] - '0']++;
		}
	}
	vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
	for (int i = 0; i < x; i++)
	{
		for(int j=n;j>= nmNeed[i][0];j--)
			for (int k = m; k >= nmNeed[i][1]; k--)
			{
					dp[j][k] = max(dp[j][k], dp[j - nmNeed[i][0]][k - nmNeed[i][1]] + 1);
			}
	}
	cout << dp[n][m];
}

发表于 2021-03-27 17:20:47 回复(0)
牛客375006号头像 牛客375006号 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    int x, U, V;
    scanf("%d %d %d", &x, &U, &V);
    int f[U + 1][V + 1];
    int v0[x], v1[x];
    memset(v0, 0, sizeof(v0));
    memset(v1, 0, sizeof(v1));
    memset(f, 0, sizeof(f));
    char s[51];
    for (int i = 0; i < x; i++){
        cin >> s;
        for (int j = 0; j < strlen(s); j++){
            if (s[j] == '0'){
                v0[i]++;
            } else {
                v1[i]++;
            }
        }
    }
    for (int k = 0; k < x; k++) {
        for (int u = U; u >= v0[k]; u--) {
            for (int v = V; v >= v1[k]; v--) {
                f[u][v] = max(f[u][v], f[u - v0[k]][v - v1[k]] + 1);
            }
        }
    }
    cout << f[U][V];
    return 0;
}
发表于 2017-10-24 02:53:08 回复(0)
nicklhk头像 nicklhk 
//经典的二维背包问题
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
	int x, n, m;
	cin >> x >> n >> m;
	vector<string> svec(x);
	for (int i = 0; i < x; ++i)
		cin >> svec[i];
	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
	int one = 0;
	int zero = 0;
	for (int i = 0; i < x; ++i)
	{
		one = zero = 0;
		for (int j = 0; j < svec[i].size(); ++j)
		{
			if (svec[i][j] == '0')
				++zero;
			else
				++one;
		}
		for (int j = n; j >= zero; --j)
		{
			for (int k = m; k >= one; --k)
			{
				dp[j][k] = max(dp[j - zero][k - one] + 1, dp[j][k]);
			}
		}
	}
	cout << dp[n][m] << endl;
}

发表于 2017-07-27 21:16:32 回复(0)
hanking头像 hanking 
回溯法的会还是比较好理解，动态规划没有做。
package 全国模拟卷2;
import java.util.Scanner;

public class Main_7 {
	static int ans=0;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext())
		{
			int x=sc.nextInt();
			int n=sc.nextInt();
			int m=sc.nextInt();
			String []strArr=new String[x];
			for(int i=0;i<x;i++)
			{
				strArr[i]=sc.next();
			}
			creat(strArr, n, m,x);
		}
		sc.close();		
	}
	public static void creat(String []strArr,int n,int m,int x)
	{
		int bits[]=new int [x];
		for(int i=0;i<x;i++)
			bits[i]=-1;
		System.out.println(creat_word(strArr, n, m, x,bits));
		
	}
	
	public static int  creat_word(String []strArr,int n,int m,int x,int []bits)
	{	int num=0;
	
		if(x==0)
		{			
			return 0;
		}
		if(n<0||m<0)			
			return 0;
		
		int bit_1=0;
		int bit_0=0;
		
		if(bits[x-1]>=0)
		{
			bit_0=bits[x-1];
			bit_1=strArr[x-1].length()-bit_0;			
		}
		else {
			bit_0=getbits(strArr[x-1], '0');
			bits[x-1]=bit_0;
			bit_1=strArr[x-1].length()-bit_0;
		}
		
		if(n-bit_0>=0&&m-bit_1>=0)
			
			num=creat_word(strArr, n-bit_0, m-bit_1, x-1,bits)+1;
		
		num=Math.max(num, creat_word(strArr, n, m, x-1,bits));
		
		return num;
	}
	public static int getbits(String str,char ch)
	{
		int num=0;
		for(int i=0;i<str.length();i++)
			if(str.charAt(i)==ch)
				num++;
		return num;
	}
}


发表于 2017-07-17 21:47:42 回复(0)
rs勿忘初心头像 rs勿忘初心
#include<iostream>
#include<string.h>
using namespace std;
int main()
  {
     int X,N,M;
     cin>>X>>N>>M;
     char s[51];    // 注意要定义大小[51]
     int n[20]={0},m[20]={0},dp[501][501]={0};    //注意要赋初值
     for(int i=0;i<X;i++)
       { 
          cin>>s;
          for(int j=0;j<strlen(s);j++)
            {
               if(s[j]=='0')
                   n[i]++;
               else
                   m[i]++;
            }
       }
    for(int i=0;i<X;i++)
       {
          for(int j=N;j>=n[i];j--)   //注意是小于等于
            {
               for(int k=M;k>=m[i];k--)
                { 
                   dp[j][k]=max(dp[j][k],dp[j-n[i]][k-m[i]]+1);
                }
            }
       }  
    cout<<dp[N][M]<<endl;
  }
发表于 2017-05-26 21:39:42 回复(0)
poluner头像 poluner
枚举子集不就行了，O(2^x) 

	#include<bits/stdc++.h>
using namespace std;
char s[50+5];
int a[20+5],b[20+5];
int main(){
    int x,n,m;scanf("%d%d%d",&x,&n,&m);
    for(int i=0;i<x;i++){
        a[i]=b[i]=0;
        scanf("%s",s);
        for(char* p=s;*p!=NULL;p++){
            if(*p=='0')a[i]++;
            else b[i]++;
        }
    }

    int maxc=0;
    for(int i=1;i<=(1<<x)-1;i++){
        int sa=0,sb=0,cnt=0;
        for(int j=0;j<x;j++){
            if(i&(1<<j))sa+=a[j],sb+=b[j],cnt++;
        }
        if(sa<=n&&sb<=m)maxc=max(maxc,cnt);
    }
    printf("%d\n",maxc);

}

编辑于 2017-04-18 15:42:00 回复(0)
Scruel头像 Scruel 
 import java.util.Scanner;

/**
 * 三维背包
 * Created by Scruel on 2017/3/29.
 * Personal blog : http://blog.csdn.net/scruelt
 * Github : https://github.com/scruel
 */
public class CreateNewWorld {

        static int x;
        static int n;//0
        static int m;//1
        static int[] item0;
        static int[] item1;

        static int solve() {
                int[][][] dp = new int[x + 1][m + 1][n + 1];

                for (int i = 0; i < x; i++) {
                        for (int j = 0; j <= m; j++) {
                                for (int k = 0; k <= n; k++) {
                                        //ok
                                        if (item1[i] <= j && item0[i] <= k)
                                                dp[i + 1][j][k] = Math.max(dp[i][j][k], dp[i][j - item1[i]][k - item0[i]] + 1);
                                        else
                                                dp[i + 1][j][k] = dp[i][j][k];

                                }
                        }
                }
                return dp[x][m][n];
        }

        public static void main(String[] args) {
                Scanner input = new Scanner(System.in);
                x = input.nextInt();
                n = input.nextInt();
                m = input.nextInt();
                item0 = new int[x];
                item1 = new int[x];

                input.nextLine();
                for (int i = 0; i < x; i++) {
                        String s = input.nextLine();
                        for (int j = 0; j < s.length(); j++) {
                                if (s.charAt(j) == '0')
                                        item0[i]++;
                                else
                                        item1[i]++;
                        }
                }
                System.out.println(solve());
        }
}

编辑于 2017-03-29 17:57:29 回复(1)
Friday_希尔瓦娜斯头像 Friday_希尔瓦娜斯 
//也不晓得跟我一样，在做这道题目之前完全没有接触过0-1背包问题的人有多少。
//为了理解这一道题，不得不说煞费苦心的百科查了不少的文章，算是明白了0-1背包问题的一点点皮毛了吧。
//接下来是我自己搜集的有关入门的一些小结。ps：当然基本上是别人总结过的，我只是把自己理解过了的搬运了过来而已
 /*
 * 基本的0-1背包问题：
 * 已知有N类物品，每类物品都只有一件，对应的重量为w[i],价值为v[i]。
 * 背包最多承重为W，在不超出承重范围的前提下，求能拿的物件的最大价值为多少
 * 
 *这是DP的一个经典实例，可以用动态规划求解
 *设dp(i,j)表示对于前i件物品，背包剩余容量为j时，能取得的最大价值
 *状态转移方程：dp(i,j) = Max(dp(i-1,j), dp(i-1,j-w[i])+v[i])
 *注：   dp(i-1,j)          -----》                dp(i,j)，即不拿第i件物品
 *	 dp(i-1,j-w[i])     -----》                dp(i,j)，即拿第i件物品
 
 * 当物品数量很多，背包的容量很大时,这时要用二维数组往往是不现实的
 * 我们可以进行空间压缩，使用一维数组实现
 * 状态转移方程：
 * dp(j)=Max(dp(j),dp(j-w[i])+v[i])
 * 注：对于背包的容量要采用倒序的方式！
 */

/*
 * 二维背包问题：
 * 对于每件物品,当选择这件物品必须同时付出两种代价；
 * 对于每种代价都有一个可付出的最大值（背包容量）。 
 * 问怎样选择物品可以得到最大的价值。
 * 设第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在此均采用倒序！
 * 
 * 例题说明：
 * 众所周知计算机代码底层计算都是0和1的计算，牛牛知道这点之后就想使用0和1创造一个新世界！
 * 牛牛现在手里有n个0和m个1，给出牛牛可以创造的x种物品，每种物品都由一个01串表示。
 * 牛牛想知道当前手中的0和1可以最多创造出多少种物品。 
 * 等价对应：
 * n             	---------         	背包容量，u
 * m				---------			背包容量，v
 * x				---------			物品个数
 * item[i].0的个数	---------			物品i对应u部分的容量
 * item[i].1的个数	---------			物品i对应v部分的容量
 * 最多创造的物品种数	---------			可得到的最大价值（此时物品的价值w[i]=1）
 */

 //另外常见的还有完全背包问题以及多重背包问题，就不啰嗦了，花点时间，至少在理解上，问题应该不是很大
 //感觉难的还是怎么把一个题目抽象到对应背包问题的模型上来，以及相关代码实现的优化。
import java.util.*; 
public class dim_2_bag {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int x = sc.nextInt();
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] zero = new int[x];
            int[] one = new int[x];
            String item;
            for(int i=0;i<x;i++) {
                item = sc.next();
                int cnt = 0;
                for(int j=0;j<item.length();j++) {
                    if(item.charAt(j) == '0') {
                        cnt++;
                    }
                }
                zero[i] = cnt;
                one[i] = item.length()-cnt;
            }
            int[][] dp = new int[n+1][m+1];
            for(int i=0;i<x;i++) {
                for(int j=n;j>=zero[i];j--) {
                    for(int k=m;k>=one[i];k--) {
                        if(dp[j][k] < dp[j-zero[i]][k-one[i]]+1) {
                            dp[j][k] = dp[j-zero[i]][k-one[i]]+1;
                        }
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    }
}

编辑于 2017-03-25 21:25:39 回复(4)
路过的熊头像 路过的熊 
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
    char s[51];
    int X, N, M, n[21] = { 0 }, m[21] = { 0 }, dp[501][501] = { 0 };   
    cin >> X >> N >> M;
    for (int i = 1; i <= X; i++){
        cin >> s;
        for (int j = 0; j < strlen(s); j++){
            if (s[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] = max(dp[j][k], dp[j - n[i]][k - m[i]] + 1);
    //二维背包，使用动态规划求dp数组
    cout << dp[N][M];
    return 0;
}
编辑于 2017-03-24 17:39:48 回复(5)
Mr_Robot头像 Mr_Robot
由于给的样例太简单根本看不懂题目，以为是要用n个0和m个1搞全组合，后来才发现是你应该要能利用0和1拼出不相同的字符串，但是这些字符串必须是已经给出的x个字符串中的某一个。
发表于 2017-03-25 22:57:07 回复(4)
Python
YYQ-SHU头像 YYQ-SHU
经过我的仔细判断，同样地算法，但是用Python永远没法通过，最多运行到70%的case就超时了。 我尽力了。。。。。 
def creatNewWorld():
    firstline = input()
    x, n, m = [int(n) for n in firstline.split()]
    zeros = [ 0 for i in range(x)]
    ones = [ 0 for i in range(x)]
    for i in range(x):
        item = str(input())
        zeros[i], ones[i] = count0and1(item)

    val = [[0 for i in range(m + 1)] for j in range(n + 1)]
    for k in range(1,x+1):
        for i in range(n, zeros[k-1] - 1, -1):
            for j in range(m, ones[k-1] - 1, -1):
                    val[i][j] = max(val[i][j], 1 + val[ i-zeros[k-1] ][ j-ones[k-1] ])

    print(val[n][m])


def count0and1(item):
    c1 = 0
    for n in item:
        if int(n) == 1:
            c1 += 1
    return len(item) - c1, c1

creatNewWorld()

编辑于 2017-09-07 21:38:44 回复(1)
Python
feifei121头像 feifei121 
总是提示 运行超时:
您的程序未能在规定时间内运行结束，请检查是否循环有错或算
法复杂度过大。 case通过率为70.00%。
明明复杂度和其他人的一样啊
# -*- coding: cp936 -*-
x = raw_input().split()
x1 = int(x[0])
x2 = int(x[1])
x3 = int(x[2])
w0 = []
w1 = []
for i in range(x1):
 l.append(raw_input())
for i in range(len(l)):
   w0.append(l[i].count('0'))
   w1.append(len(l[i])-w0[i])
bag0 = range(0,x2+1)
bag1 = range(0,x3+1)
f = [[0 for i in range(x3+1)] for j in range(x2+1)] l =[]
for i in range(x1-1,-1,-1):
    for j in range(x2,-1,-1):#2 1 0 
        for k in range(x3,-1,-1):#0
          if bag1[k] < w1[i] or bag0[j] < w0[i]:
            break
          else:                
            f[j][k] = max(f[j][k],1 + f[bag0[j]-w0[i]][bag1[k]-w1[i]])
print f[x2][x3]

发表于 2017-07-08 21:01:45 回复(1)
漏网之鱼1头像 漏网之鱼1
死活不对，原来发现看错题目了，是多少种不是多少个，背包算法递归的方法。（动态规划方法的数组下标不知道啥意思）
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<string> a;
int maxs, x, n, m;
vector<int> b;    //记录每个物体的个数
void dfs(int n0, int m1, int index)
{
if (n0>n || m1>m){
return;
}
else{
for (int j = 0; j<x; j++){
(b[j]>=2) return; //种数重复了，return不算。            
        }
        int count=0;
        for(int j=0;j<x;j++)  {
            if(b[j]==1)
              count++;  
        }
        if(maxs<count)
            maxs=count;
for (int i = index; i<x; i++){
b[i]++;
string s = a[i];
int num0 = 0;
int num1 = 0;
for (int i = 0; s[i] != '\0'; i++)
{
if (s[i] == '0')
num0++;
if (s[i] == '1')
num1++;
}
dfs(n0 + num0, m1 + num1, i);
b[i]--;
}
}
}
int main()
{
cin >> x >> n >> m;
string s;
for (int i = 0; i<x; i++)
{
cin >> s;
a.push_back(s);
b.push_back(0);
}
maxs = 0;
dfs(0, 0, 0);
cout << maxs;
return 0;
}
发表于 2017-06-02 22:51:02 回复(0)
sky_han头像 sky_han 
背包问题的变形。。。刚开始真的是读不懂题。。。

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int main()
{
 int x,n,m;
 cin>>x>>n>>m;
 vector<string>v(x);
 for(int i=0;i<x;i++)
     cin>>v[i];
     int z[x];
    memset(z,0,sizeof(z));
     int o[x];
     memset(o,0,sizeof(o));
 for(int i=0;i<x;i++)
  for(int j=0;j<v[i].length();j++)
      if(v[i][j]=='0')
          z[i]++;
     else
         o[i]++;
    int dp[n+1][m+1];
    memset(dp,0,sizeof(dp));
  for(int i=0;i<x;i++)
      for(int j=n;j>=z[i];j--)
          for(int k=m;k>=o[i];k--)
            dp[j][k]=max(dp[j][k],dp[j-z[i]][k-o[i]]+1);
    cout<<dp[n][m]<<endl;
    return 0;      
}

发表于 2017-03-29 23:27:50 回复(1)
TheBestIsYetToCome-头像 TheBestIsYetToCome-
//就是普通的0-1背包问题吧，注意这里的容量m跟n都需要判断就行了。
//不过考试的时候没做出来T T
#include <iostream>
#include <stdio.h>
#include <vector>
#include  <string>
#include <map>
using namespace std;

struct Str{
string s;
int cnt1,cnt0;
};

vector<Str> str(21);
int most_cre(int m,int n,int i){
if(i<0) return 0; 
if(str[i].cnt1<=m&&str[i].cnt0<=n){
return max(most_cre(m-str[i].cnt1,n-str[i].cnt0,i-1)+1,most_cre(m,n,i-1));
}else{
return most_cre(m,n,i-1);
}
}

int main()
{

    int cnt[2];
int n;
cin >> n>>cnt[0]>>cnt[1];
for(int i=0;i<n;i++){
cin>>str[i].s;
str[i].cnt0=str[i].cnt1=0;
for(int j=0;j<=str[i].s.size();j++){
if(str[i].s[j]=='0')  ++str[i].cnt0;
else if(str[i].s[j]=='1')++str[i].cnt1;
}
}
cout<<most_cre(cnt[1],cnt[0],n-1)<<endl;

    return 0;
}

发表于 2017-03-24 16:02:55 回复(1)
繁星2012头像 繁星2012
根据最子序列的思想，求出符合条件的最大子序列的个数 
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int countChar(string str, char c)
{
	int n=0;
	for (int i=0 ;i<str.length() ; ++i)
	{
		if (str[i] == c)
		{
			n++;
		}
	}
	return n;
}

int main()
{
	int n,m,strNum;
	string strTmp;
	vector<string> obj;
	vector<int> n0,n1;

	cin>>strNum>>n>>m;

	for (int i=0; i<strNum;++i)
	{
		cin>>strTmp;
		obj.push_back(strTmp);
		n0.push_back(countChar(strTmp,'0'));
		n1.push_back(countChar(strTmp,'1'));
	}

	int max = 0;
	vector<int> num(strNum,1);

	for (int i=1; i<strNum; ++i)
	{
		int t0 = n0[i];
		int t1 = n1[i];

		for (int j=0; j<i; ++j)
		{
			t0 += n0[j];
			t1 += n1[j];

			if (t0 <= n && t1 <= m && num[j]+1 > num[i]) 
			{
				num[i] = num[j] + 1;

				if (max < num[i])
				{
					max = num[i];
				}

			}
			else
			{
				t0 -= n0[j];
				t1 -= n1[j];
			}
		}

		
	}

	cout<<max<<endl;

	return 0;
}

编辑于 2017-03-24 14:39:40 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 动态规划 测试开发工程师 大数据开发工程师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
17条回答 8583浏览

热门推荐

通过挑战的用户

相关试题

创造新世界

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号