优化的基于时间的算法

Question

我正在写一个算法对于这个问题，算法很简单，我已经写的代码，但我看不到任何可能的优化：

我有一个有100个石头和5个使用它来装饰沙堡的小孩。 每个孩子反复拿起一块石头每一定的时间跨度，每个孩子都是独立于他人，更多的孩子可以拿起在同一时间一块石头，有5个孩子合计：

• 埃里克挑一块石头，每5分钟
• 马克拿起石每10分钟
• 拉拉拿起石每7分钟
• 艾玛拿起石每3分钟
• 弗兰克拿起石每3分钟

我们需要多少分钟才​​能清空存储桶？要更加清楚：10分钟后，埃里克有两块石头（分钟5和分钟10），而艾玛有3块石头（分钟3,6和9）。

所以，10分钟后的儿童有总共2 + 1 + 1 + 3 + 3 = 10结石，有90个结石铲斗

这是我的代码（Python 3中）：

children_rate = [3, 3, 5, 7, 10] 
bucket = 100 

minutes = 0 

while True: 
    minutes += 1 
    for child in children_rate: 
     if minutes % child == 0: 
      bucket -= 1 
      if bucket == 0: 
       print('bucket empty in',minutes,'minutes') 
       exit() 

此代码有效，在这种情况下，所需的分钟数是91，但我不能使用此代码处理一百万个石头和500个孩子的桶。

我可以看到的唯一优化是在总和/加操作中转换mod操作，因为分割/乘法更昂贵。我可以使用numpy数组等等，但没有什么能够真正加速这个过程。

我试着将问题适应于我的算法教科书中描述的一些典型的知识问题，但没有运气。

Answer 1

有一两件事你可以做的是对的答案二进制搜索。

假设答案是X分钟。 然后你知道每个孩子在那段时间会带多少石头。 如果结果总数少于预期，X需要更高。 否则，在下半部分搜索。

在代码：

children_rate = [3, 3, 5, 7, 10] 
bucket = 100 

lo, hi = 0, bucket * max (children_rate) 
while lo < hi: 
    me = (lo + hi) // 2 
    if sum (me // i for i in children_rate) < bucket: 
     lo = me + 1 
    else: 
     hi = me 

print (lo) 

Answer 2

您可以调整算法，以便在给定的分钟数内计算所有孩子已经使用了多少宝石。

def compute_stones(minutes) 
    stones = 0 
    for child in children_rate: 
     stones += minutes // child # integer division 
    return stones 

然后，你可以做一个二进制印章找到分钟的编号，在这些石头= 100

Answer 3

每个孩子挑选在一段时间石头，所有的孩子一起捡石头，其中有一个周期，以及一些模式。这种模式的时期是每个孩子时期的Least common multiple。它可以用几种方法计算，但在这种情况下，我们使用每个周期的因子分解。

3 = 3 
5 =  5 
7 =  7 
10 = 2 * 5 

所以常见的时期是210 = 2 * 3 * 5 * 7。在这段时间里，埃里克挑选42块石头，马克挑选21块石头，拉拉挑选30块石头，埃玛和弗兰克挑选70块石头。这是每210分钟233石头。如果你在一个桶里有100万块石头，他们会在901110分钟内挑出999803块石头，然后你将运行你原来的代码，用于其余的197块石头。很简单，不是吗？