一道困扰我的算法面试题

抛砖引玉吧 假设把100个人每5个人一组测一次，测20次能把问题变成最多25个人里找5个人 假设100个人每3个人一组，测33次能把问题变成15个人里找5个人 5组每组5个人 第一种情况，假设每组再测一次，前2个人，如果中了的话，每组再测一次，最多再测10次就出来了 第二种情况，如果中间有没中的后面三个人前两个人再测一次，最多15次就都测出来了 4组每组5个人 按2个人一组，20个人分10组，测出来5组，再测5次，也是最多再15次就都测出来了 20+15，35吧 不过其实应该有能优化的部分

7 盒吧，2^7 = 128 用2进制表示所有人，思路是这样

def main():     for p in range(1, 5 + 1):         for n in range(p, 100 + 1):             spend(n, p)     print(table)     print("从100人中找出5位感染者需要使用 {0} 个试剂盒".format(table[100, 5])) if __name__ == '__main__&(688)#39;:     main()      代码运行的结果是23，我也不知道对不对. 不怎么刷算法题，如果有错误请用善意的语言提出哈😀.

下面附上Python代码： import numpy as np table = np.zeros([100 + 1, 5 + 1], dtype=int) def spend(n, p):     assert 1 <= p <= n     if n == p:         return 0     minSpend = 10e5     for k in range(1, n - p + 1):         if p == 1:             maxSpend = table[max(k, n - k), 1] + 1         else:             maxSpend = table[n - k, p] + 1             if k < p:                 for i in range(max(1, p + k - n), k + 1):                     currentSpend = table[k, i] + table[n - k, p - i] + 1                     if currentSpend > maxSpend:                         maxSpend = currentSpend             else:                 maxSpend = max(maxSpend, table[k, p])                 for i in range(max(1, p + k - n), p):                     currentSpend = table[k, i] + table[n - k, p - i] + 2                     if currentSpend > maxSpend:                         maxSpend = currentSpend         if maxSpend < minSpend:             minSpend = maxSpend     table[n, p] = minSpend

   b) 当 k >= p 时（此时k人混血检测结果如果为阳，N-k人中不确定是否还存在感染者）       如果(k人检测结果为阴性){           S(N, p) = S(N-k, p) + 1       }       否则{           再拿取一个试剂盒，将N-k人的血液混合检测;           如果(N-k人检测结果为阴性){               S(N, p) = S(k, p) + 2，加二表示已经用掉两个试剂盒           }           否则{               k人中和N-k人中都有感染者.               和上述某个讨论解决方法一致.           }       }       最后，取各个情况最大值.    ③ 对不同k得到的k个S取值，取S的最小值即可.

隐藏条件：可以将多人的血液混合后使用一个试剂盒进行检测，有一人及以上的血液中含有病毒，则试剂盒显示为阳性，否则试剂盒显示为阴性. 思考方向：递归求解 检测过程拆解： 假设一共有N人，其中p人感染病毒（1<=p<=N），记S(N, p)表示解决问题需要花费的试剂盒数量. 1) 显然有递归边界：S(N, N) = 0，其含义是N人全感染则使用0个试剂盒就能解决问题. 2) 假设只有一位检测医生，即试剂盒的使用是串行的，不能并行使用试剂盒，只有当上一个试剂盒的结果出来后，才能去仓库拿取下一个试剂盒.    所以，检测医生当前手上的这个试剂盒只有两种使用方式：一是只检测一个人，二是从待检测人中抽取多人进行混合血液检测.    设医生从N人中随机抽取k人（1<=k<=N-p），然后将他们的血液混合后导入试剂盒，    ① 当 p = 1 时（即N中只有一人感染的情况），      如果k个人混血检测结果为阳性，说明仅有的一位感染者在这k人当中，即S(N, 1) = S(k, 1) + 1，加一是指已经耗费的一个试剂盒；如果k个人混血检测结果为阴性，说明仅有的一位感染者在剩余的N-k人当中，即S(N, 1) = S(N-k, 1) + 1.      我们使用两者最坏的情况进行计算，因此，S(N, 1) = max{S(k, 1) + 1, S(N-k, 1) + 1}.    ② 当 p > 1 时（即N中有多人感染的情况），    a) 当 k < p 时（此时不管k人混血检测结果阴阳，N-k人中肯定还存在感染者）       如果(k人检测结果为阴性){           S(N, p) = S(N-k, p) + 1       }       否则{           k人中和N-k人中都有感染者.           例如p=5，则有(1,4)(2,3)(3,2)(4,1)四种可能性，比如(1,4)这种情况成递推公式就是：           S(N, 5) = S(k, 1) + S(N-k, 4) + 1.       }       最后，取各个情况最大值.

我觉得这题有问题吧。。最少不应该是5个？最多99个？   人与人之间是独立的，暂时没想出什么相关性。。。感觉应该是期望的形式。。。

100人里5人感染，一共是C(5, 100)种情况。由于我们不知道先验概率，所以认为可能性均等，信息熵是log[C(5, 100)]。每个试剂盒有两种情况，阳性和阴性，当这两种情况概率相等时所能提供的信息熵最大，也就是log 2。最终答案 = log[C(5, 100)]/log 2，上取整得27。

27个吧

我人傻了，可能我比较蠢，我觉得是100个。这东西不能复用呀…… 或者0个，先隔离14天，然后患病的就出现症状了……

dp 丢鸡蛋问题吗？

是不是和几跑道赛马，最少几场次能得出前几名类似思路？