首页 > 试题广场 >

招聘会小礼品

[编程题]招聘会小礼品
  • 热度指数:407 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
小摩召开了一场招聘会,招聘会现场一共有N个人,Mobike公司给大家准备了一些小礼品。但是我们并不知道每个人具体喜欢什么,
现在库房共有M种小礼品,每种小礼品有Ci件,共N件。而我们大致知道每个人选择某种小礼品的概率,
即能知道Pij(编号为i的人选择第j种小礼品的概率)。现在所有人按编号依次领小礼品(第1个人先领,第N个人最后领),
领小礼品时,参加者会按照预先统计的概率告诉准备者自己想要哪一种小礼品,
如果该种小礼品在他之前已经发放完了则他会领不到小礼品,请帮我们计算出能能领到小礼品的期望人数。

输入描述:
第一行包含两个整数N(1≤N≤300),M(1≤M≤100),用单个空格隔开。表示公有N个应聘者,M种小礼品。
第二行为M个整数,依次为Ci,第i种小礼品的个数。
接下来的N行,每行M个实数,依次为Pij,第i个人选择第j种小礼品的概率。


输出描述:
一行输出期望人数。结果保留1位小数。
示例1

输入

2 2
1 1
0.3 0.7
0.7 0.3

输出

1.6

说明

(样例解释:共有4种选择(1,1),(1,2),(2,1),(2,2),概率分别为0.21、0.09、0.49、0.21,(1,1),(2,2)这两种选择只有1个人能拿到小礼品,(1,2),(2,1)这两种选择有2个人能拿到小礼品,所以期望为1*(0.21+0.21) + 2*(0.09+0.49) = 1.58,保留一位小数为1.6。)
# Algorithm: # the problem of calcu the number of prizes obtained is equal to the problem of calcu the number # of prizes left behind, that is, getPrize = N - leftPrize. # So, we can easily calcu the prob (p_k) of the prize j (j: 1~M) left with k (k: 1~C[j]) items  # after the selecting process of i (i: 1~N) interviewees in each iteration, # that is, p_k' = p_k*(1-P[i][j]) + p_(k+1)*P[i][j] def prizeGetFunc(N,M,C,P):     """"     Parameters     ----------     N :   number of interviewees     M :   kinds of the gifts     C :   number of each gift     P :   preferential matrix     """     leftPrize = 0     # initiate the number of prizes left     for j in range(M):         prizeLeftPro = [0]*C[j]+[1]  # initialize the left prob of each prize (from 0 to C[j])         for i in range(N):             prizeLeftPro[0] += prizeLeftPro[1] * P[i][j] # left 0, prizes of kind i are all given             for k in range(C[j]):                 prizeLeftPro[k] = prizeLeftPro[k]*(1-P[i][j]) + prizeLeftPro[k+1]*P[i][j] # update the p_k             prizeLeftPro[C[j]] = prizeLeftPro[C[j]]*(1-P[i][j])         for k in range(1,C[j]+1):             leftPrize += prizeLeftPro[k]*k # calculate the expected number of prizes left     getPrize = round(N-leftPrize,1)     return getPrize
N = int(raw_input())     M = int(raw_input())     C = map(int,raw_input().split())     P = [[map(int,raw_input().split())] for i in range(N)]     getPrize = prizeGetFunc(N,M,C,P)     print getPrize        

编辑于 2018-08-01 20:54:19 回复(1)
import itertools
# 能实现,但是耗费时间太多,先占个坑等想出来了再补充吧- -
nm = input().split()
n, m = int(nm[0]), int(nm[1])
gifts_types = list(range(m))
gifts_num = list(map(int, input().split()))
prob_gifts = []
total_exp = 0
for _ in range(n):
    prob_gifts.append(list(map(float, input().split())))
for choice in itertools.product(gifts_types, repeat=n):
    temp_dict = {}
    prob_temp = 1
    for j in range(n):
        if choice[j] not in temp_dict.keys():
            temp_dict[choice[j]] = choice.count(choice[j])
        prob_temp *= prob_gifts[j][choice[j]]
    if prob_temp > 0:
        num_temp = 0
        for k in temp_dict.keys():
            num_temp += min(temp_dict[k], gifts_num[k])
    else:
        continue
    total_exp += prob_temp * num_temp
print("%.1f" % total_exp)

发表于 2018-10-04 22:59:12 回复(0)