[编程题]创造新世界
- 热度指数：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
#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)
#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)
//经典的二维背包问题
#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)
回溯法的会还是比较好理解，动态规划没有做。
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)
#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)
枚举子集不就行了，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)
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)
//也不晓得跟我一样，在做这道题目之前完全没有接触过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)
经过我的仔细判断，同样地算法，但是用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)
总是提示 运行超时:
您的程序未能在规定时间内运行结束，请检查是否循环有错或算
法复杂度过大。 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)
死活不对，原来发现看错题目了，是多少种不是多少个，背包算法递归的方法。（动态规划方法的数组下标不知道啥意思）
#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)
背包问题的变形。。。刚开始真的是读不懂题。。。
#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)
//就是普通的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)
根据最子序列的思想，求出符合条件的最大子序列的个数
#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)
问题信息
通过挑战的用户
-
2023-01-02 23:09:25
-
2022-09-19 21:39:37
-
2022-06-10 11:10:45
-
2022-06-09 22:41:10
-
2021-07-13 17:15:01
相关试题
-
评论(7)
-
评论(1)
-
评论(29)
-
评论(32) 来自【2017】牛客模考（二...
-
评论(16) 来自【2017】牛客模考（二...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
