首页 > 试题广场 >

工作安排

[编程题]工作安排

热度指数：2360 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。

输入描述:

输入数据有n+1行： 第一行为工程师人数n(1 ≤ n ≤ 6) 接下来的n行，每行一个字符串表示第i(1 ≤ i ≤ n)个人能够胜任的工作(字符串不一定等长的)

输出描述:

输出一个整数，表示有多少种不同的工作安排方案

示例1

输入

6 012345 012345 012345 012345 012345 012345

输出

算法知识视频讲解

Python

牛客558275203号

n = int(input())
canDo = [input() for _ in range(n)] 
done = [False] * 6

def solve(i):
    
    if i == n:
        return 1
    
    res = 0
    for k in range(6):
        if not done[k] and (str(k) in canDo[i]):
            done[k] = True
            res += solve(i+1)
            done[k] = False
    return res

print(solve(0))

回溯法Python3版本。

编辑于 2020-04-07 11:26:27 回复(0)

Python

绝无*仅有

def getData():
n = eval(input("请输入工程师人数:"))
engineerDic = {}
for m in range(1,n+1):
job = input("第%d位工程师胜任工作:"%m)
engineerDic[m]=job
return engineerDic

def workArray(workList,i):
global num
if i < len(engineerDic.keys())+1:
works = engineerDic[i]
for work in works:
if eval(work) in workList:
workList.remove(eval(work))
i += 1
workArray(workList,i)
i-=1
workList.append(eval(work))
else:

num+=1

engineerDic = getData()
num = 0
i = 1
workList = [0, 1, 2, 3, 4, 5]

workArray(workList,i)
print(num)

发表于 2017-11-18 17:34:54 回复(0)