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

Question

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

Two printers work in different speed. The first printer produces one paper in x minutes, while the second does it in y minutes. To print N papers in total, how to distribute the tasks to those printers so the printing time is minimum?

练习给了我三个输入 x,y,N 并要求输出最小时间。

input data:

1 1 5

3 5 4

answer:

3 9

我尝试将第一台打印机的任务设置为 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))))

尽管在某些极端情况下您可能需要稍微更改它。

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

Algorithm for distributing tasks to two printers?

python

algorithm

distribution

time-complexity