并行和顺序进程的最小执行时间问题

问题描述 投票：0回答：2

问题。在工厂制造一个设备，必须经过两道工序。程序 A 由 A 机器人完成，B 由 B 机器人完成。所有机器人的执行时间可能不同。问题：编写一个算法（公式）来描述创建 n 个细节所需的最短时间。 给出的是：

  • Arobots执行时间列表
  • 机器人执行时间列表
  • 生产的产品数量

例如

6      # number of devices to produce
3      # number of A robots
1 3 2  # list of the execution time of A robots
2      # number of B robots
3 2    # list of the execution time of B robots
Answer in this case:
9

原题https://www.eolymp.com/uk/problems/161

我尝试过编写 Python 代码。但是这个公式/算法的准确率是 35%。

import math

n = int(input())
An = int(input())
A = [int(num) for num in input().split()]
A.sort()
Bn = int(input())
B = [int(num) for num in input().split()]
B.sort()


a = 0
for i in A:
    a += 1/i
a = n/a

b = 0
for i in B:
    b += 1/i
b = n/b

c = min(min(A), min(B))

ans = math.ceil(max(a, b)) + c
print(ans)

似乎可以使用二进制搜索来解决问题，但是我无法编写适当的函数来获取特定时间的最大细节。有这个带有二进制搜索的实现。准确度 20%.

import math
def num(m, A, B):
    a = 0
    for i in A:
        a += m // i

    b = 0
    for i in B:
        b += m // i
    return min(a, b)

n = int(input())
An = int(input())
A = [int(num) for num in input().split()]
Bn = int(input())
B = [int(num) for num in input().split()]




l = 0
r = max((max(A)*n), (max(B)*n)) + min(min(A),min(B))





while l < r:
    m = (r + l) // 2
    k = num(m, A, B)                    #m // x + m // y
    if k < n - 1:
        l = m + 1
    else:
        r = m

print(l+max(A))

@btilly

A = []
A.sort()
B = []
B.sort()
n = 

a = []
time = 0
while len(a) < n:
    time += 1
    for i in range(len(A)):
        if time%A[i]==0:
            a.append((time, i))
            if len(a) >= n:
                break


b = []
time = A[0]
while len(b) < n:
    time += 1
    for i in range(len(B)):
        if time%B[i]==0:
            b.append((time, i))
            if len(b) >= n:
                break
b = b[::-1]
#print(b)
c = []
for i in range(len(a)):
    c.append(a[i][0]+b[i][0])

print(max(c))

以下代码在 10% 的测试中正常工作（在网站上，检查它）。突然，我无法给出不正确的数据输入（只是不知道）。

algorithm array-formulas
2个回答
0
投票

您想找到第一个

t
，这样我们就可以在那个时间生产
n
设备。

我们的第一个观察是，给定时间

t
和最佳解决方案，我们不会通过尽快完成
A
的所有生产而使情况变得更糟。

我们的第二个观察是，我们也不会通过尽可能晚地（同时保持时间表）完成

B
的所有消费而使情况变得更糟。

我们的第三个观察结果是，由于 

A
机器人的输出是相同的，我们坚持认为 
A
产生的第一个东西是 
B
最先消耗的东西，
A
产生的第二个东西是
B
等消耗的第二件事。

现在让我们举个例子。

n = 6
A = [1, 2, 3]
B = [2, 3]


A
能多快生产
6
物品？我将其作为 
(time, robot)
.

的数组给出 
A_produced = [(1, 0), (2, 0), (2, 1), (3, 0), (3, 2), (4, 0)]


B
多快可以消耗6件物品？我将其作为 
(time_from_end, robot)
.

的数组给出 
B_consumed_reverse = [(2, 0), (3, 1), (4, 0), (6, 0), (6, 1), (8, 0)]

现在我们反转它。

B_consumed = [(8, 0), (6, 1), (6, 0), (4, 0), (3, 1), (2, 0)]

现在我们配对。

[(1, 0), (2, 0), (2, 1), (3, 0), (3, 2), (4, 0)]
[(8, 0), (6, 1), (6, 0), (4, 0), (3, 1), (2, 0)]
  9       8       8       7       6       6

第三行是一组下限，如果 

i
的第 
A
项的生产与 
B
的下限消耗一致。我们最大的下界是
9
。那是我们的最高下界，也是答案。

这也是答案可以通过从

9
中给出的信息中找到最佳解决方案来证明。我们通过将结束时间设置为
9
，记录
A
中的每个机器人何时结束，并记录
B
中的每个机器人何时开始。

这个程序总是给出正确答案，所以没有必要实际去做。但这是这个例子的时间表。

time  robots A start  robots A finish  robots B take  robots B finish
  0          [0,1,2]               []             []               []
  1              [0]              [0]            [0]               []
  2              [0]            [0,1]             []               []
  3              [0]            [0,2]          [0,1]              [0]
  4               []              [0]             []               []
  5               []               []            [0]              [0]
  6               []               []            [1]              [1]
  7               []               []            [0]              [0]
  8               []               []             []               []
  9               []               []             []            [0,1]

你可以看到我们及时生产

6
东西
9
，从来没有
B
需要
A
还没有生产的东西。

0
投票

解决方案：

from queue import PriorityQueue

n = int(input())
An = int(input())
A = [int(num) for num in input().split()]
Bn = int(input())
B = [int(num) for num in input().split()]


q = PriorityQueue()

for i in A:
    q.put((i, i))

times = []
for i in range(0, n):
    pair = q.get()
    times.append(pair[0])
    q.put((pair[0]+pair[1], pair[1]))

q = PriorityQueue()

for i in B:
    q.put((i, i))

max_time = 0
for i in range(n-1, -1, -1):
    pair = q.get()
    times[i] += pair[0]
    q.put((pair[0]+pair[1], pair[1]))
    if (times[i] > max_time):
        max_time = times[i]

print(max_time)

答案（Java）来自： https://java.mazurok.com/?p=3778

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.