将任务分配给两台打印机的算法？

Question

我做编程练习网上，我发现这样一个问题：

两台打印机在不同的转速下工作。第一台打印机在x分钟内生成一张纸，而第二台打印机在y分钟内生成一张纸。要总共打印N份纸张，如何将这些任务分配给这些打印机，以便打印时间最短？

演习给了我三个输入x，y，N并要求最小时间作为输出。

输入数据：

答案：

我试图设置第一打印机任务如a，以及第二台打印机的任务作为N-a。最有效的打印方式是让它们有相同的时间，所以最小时间为（（n * b）/（a + b））+ 1。然而这个公式是错误的。

然后我试图用蛮力的方式来解决这个问题。我首先在a和b中区分哪一个更小（更快）。然后我一直添加一张纸到更快的打印机。当该打印机所需的时间比打印另一台打印机的一张纸的时间长时，我将一张纸放到较慢的打印机上，并减去打印速度更快的时间。

代码如下：

def fastest_time (a, b, n): 
""" Return the smalles time when keep two machine working at the same time. 
    The parameter a and b each should be a float/integer referring to the two 
    productivities of two machines. n should be an int, refering to the total 
    number of tasks. Return an int standing for the minimal time needed.""" 

    # Assign the one-paper-time in terms of the magnitude of it, the reason 
    # for doing that is my algorithm is counting along the faster printer. 
    if a > b: 
     slower_time_each = a 
     faster_time_each = b 

    elif a < b : 
     slower_time_each = b 
     faster_time_each = a 

    # If a and b are the same, then we just run the formula as one printer 
    else : 
     return (a * n)/2 + 1 

    faster_paper = 0 
    faster_time = 0 
    slower_paper = 0 

    # Loop until the total papers satisfy the total task 
    while faster_paper + slower_paper < n: 

     # We keep adding one task to the faster printer 
     faster_time += 1 * faster_time_each 
     faster_paper += 1 

     # If the time is exceeding the time needed for the slower machine, 
     # we then assign one task to it 
     if faster_time >= slower_time_each: 
      slower_paper += 1 
      faster_time -= 1 * slower_time_each 

    # Return the total time needed 
    return faster_paper * faster_time_each 

它的工作原理时N小或x和y是大的，但它需要大量的时间（超过10分钟我猜的）来计算时x和y非常小，即输入是1 2 159958878。

我相信有一个更好的算法来解决这个问题，任何人都可以给我一些建议或提示吗？

Answer 1

鉴于形式

x, y, n = 1, 2, 159958878 

这应该工作

import math 
math.ceil((max((x,y))/float(x+y)) * n) * min((x,y)) 

这适用于所有的样本输入的输入。

In [61]: x, y, n = 1,1,5 

In [62]: math.ceil((max((x,y))/float(x+y)) * n) * min((x,y)) 
Out[62]: 3.0 

In [63]: x, y, n = 3,5,4 

In [64]: math.ceil((max((x,y))/float(x+y)) * n) * min((x,y)) 
Out[64]: 9.0 

In [65]: x, y, n = 1,2,159958878 

In [66]: math.ceil((max((x,y))/float(x+y)) * n) * min((x,y)) 
Out[66]: 106639252.0 

编辑：

这并不由@Antti即x, y, n = 4,7,2提到的情况下工作。

原因是我们首先考虑的是较短的时间。因此，解决方案是找到两个值，即考虑更短的时间并考虑更长的时间，然后选择哪个结果值更小。

所以，这适用于所有情况，包括@ Antii的

min((math.ceil((max((x,y))/float(x+y)) * n) * min((x,y)), 
    math.ceil((min((x,y))/float(x+y)) * n) * max((x,y)))) 

虽然可能有一些极端的情况下，你可能需要改变一点点。