Алгоритм распределения задач на два принтера?

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.

Причина в том, что мы сначала рассматриваем меньшее время.Таким образом, решение состоит в том, чтобы найти как значения, т. Е. С учетом меньшего времени и с учетом большего времени, а затем выбрать, какое из результирующих значений меньше.

Таким образом, это работает для всех случаев, в том числе @ Антии-х

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)))) 

Хотя там могут быть некоторые крайние случаи, когда вы, возможно, придется изменить его немного.