创造新世界

[编程题]创造新世界

热度指数：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

输出

算法知识视频讲解

Python

YYQ-SHU

经过我的仔细判断，同样地算法，但是用Python永远没法通过，最多运行到70%的case就超时了。我尽力了。。。。。

http://blog.csdn.net/yyqhere/article/details/77886680

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

总是提示 运行超时:
您的程序未能在规定时间内运行结束，请检查是否循环有错或算
法复杂度过大。 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]])