Статья Автор: Логинов Даниил

22 или 24 я не понмю

Определите максимальную продолжительность отрезка времени (в мс),
в течение которого возможно одновременное выполнение максимального количества процессов, при условии,
что все независимые друг от друга процессы могут выполняться параллельно,
а время окончания работы всех процессов минимально.

d = {0: [{}, 0, 0]}

# считываем данные из файла
with open("22.txt") as file:
    for i in file: # или file.readlines()
        x, time, *y = map(int, i.replace(";", " ").split())
        # при вводе "4 5 6 7" или "4 5 6;7"
        # x = 4, time = 5, y = (6, 7)
        # больше чисел при вводе => больше массив (кортеж) y
        d[x] = [set(y), time, 0]
        # зависимые процессы, время выполнения процесса, задержка (если она возможна по условию задачи)

start_end = {0: (0, 0)}  # словарь, в котором хранятся моменты старта и конца конкретного процесса
visited = {0}
while len(visited) < len(d):  # <=> пока не запишем все процессы
    for i in d:
        if any(xd not in start_end for xd in d[i][0]) or i in visited:
            # если хотя бы один из зависимых процессов не обработан, мы не можем получить результат для текущего
            # наличие процесса в проверенных
            continue
        st = max([start_end[xd][1] for xd in d[i][0]]) + d[i][2]
        # =макс(впр;впр) + задержка
        start_end[i] = (
            st + 1,       # старт
            st + d[i][1]  # конец
        )
        visited.add(i)

"""
xddd = {}
for i in start_end:
    xddd[i] = 38 - start_end[i][1]
    print(i, start_end[i])
print(xddd)
# если 37 - это минимальное время за которое должны завершится все процессы, то можно найти сдвиг для каждого процесса
# сдвиги могут быть немного больше, чем оптимальные, поэтому потом вручную надо будет их подправить
# если процесс N зависит только от M, при этом сдвиг для N не может превышать k, то и сдвиг для M не может превышать k
# если процесс N зависит от множества {M1, M2...}, при этом сдвиг для N не может превышать k, 
# то сдвиг для Mi - процесса(ов), который(ые) заканчивается(ются) позже всех, не может превышать k
# в итоге берете самые посделние процессы и строите цепочку от них (выполняя вышеперечисленные указания)
"""

tline = []       # безыдейный таймлайн. надеемся и верим, что больших чисел не будет.
visited = set()
mx = res = 0     # ответ / проммежуточный ответ
mx1 = 4          # максимальное количество процессов (если просят конкретное количество, то код ниже будет немного изменен, а переменная потеряет смысл)
while len(visited) < len(d): # пока не обработаем каждый процесс
    tline.append(0) # текущая секунда
    i = len(tline)
    for id in start_end:
        if id in visited:
            continue
        if start_end[id][0] <= i and start_end[id][1] >= i:
            tline[-1] += 1
        if start_end[id][1] <= i:
            visited.add(id)

    # ищем длину промежутка, который подходит по условию
    if mx1 < tline[-1]:
        mx1 = tline[-1]
        res = 1
        mx = 1
    elif tline[-1] == mx1:
        res += 1
        mx = max(mx, res)
    else:
        res = 0
    """
    # если n дано в задаче:
    if tline[-1] == n:
        res += 1
        mx = max(mx, res)
    else:
        res = 0
    """

# минимальное время выполнения всех процессов не должно превышать той ситуации, в которой у вас везде задержка = 0
# проверка на всякий случай
if len(tline) < 37:
    print(tline, len(tline))

# проверка, являетя ли определенный вами максимум действительным
if mx1 > 4:
    print("mx1:", mx1)

return mx if len(tline) == 37 else -1

def req(n, d, cnt, cnt0 = 0, i = 0):
    # самый примитивный перебор на свете, погнали
    # перебираем для каждого процесса сдвиг от 0 до n (или заданного ранее числа, в словаре xddd)
    # n - максимальный сдвиг
    # обычно n не сильно большой. Протестируйте на разных значениях в задаче и проследите за изменениями
    # d - данные о процессах
    # cnt - максимальное количество процессов, которые вы будете менять
    # обычно в таких задачах надо менять 0-5 процессов. Такое ограничение немного ускоряет программу
    # cnt0 - текущее количество измененных процессов (0 по умолчанию)
    # i - текущий процесс, который мы меняем (0 по умолчанию)
    if i == len(d):
        # если прошлись по всем процессам, то выводим
        return go(d)

    if cnt0 == cnt:
        d[keys[i]][2] = 0
        return req(n, d, cnt, cnt0, i + 1)

    result = -5
    for id in range(min(ddd[keys[i]], n)):
        # меняете сдвиг для keys[i]-ого процесса на id
        # где-то вне функции напишите keys = sorted(d.keys())
        d[keys[i]][2] = id
        result = max(result, req(n, d, cnt, cnt0 + int(id != 0), i + 1))
        # все это будет выполняться очень долго
        # поэтому с некоторым интервалом вы можете следить, жива ваша программа или где-то зациклилась
        # можно для начала убрать if и проверить
        if i == 0:
            print(result)

    return result

для работы со словарем xddd, его так же надо скопировать и ввести где-то вне функции
#print(go(d))
print(req(10, d, 5))

вся программа выглядит как-то так

def go(d):
    start_end = {0: (0, 0)}
    visited = {0}
    while len(visited) < len(d):
        for i in d:
            if any(xd not in start_end for xd in d[i][0]) or i in visited:
                continue
            st = max([start_end[xd][1] for xd in d[i][0]]) + d[i][2]
            start_end[i] = (
                st + 1,
                st + d[i][1]
            )
            visited.add(i)
    """
    xddd = {}
    for i in start_end:
        xddd[i] = 38 - start_end[i][1]
        print(i, start_end[i])
    print(xddd)
    """

    tline = []
    visited = set()
    mx = res = 0
    mx1 = 4
    while len(visited) < len(d):
        tline.append(0)
        i = len(tline)
        for id in start_end:
            if id in visited:
                continue
            if start_end[id][0] <= i and start_end[id][1] >= i:
                tline[-1] += 1
            if start_end[id][1] <= i:
                visited.add(id)
        if mx1 < tline[-1]:
            mx1 = tline[-1]
            res = 1
            mx = 1
        elif tline[-1] == mx1:
            res += 1
            mx = max(mx, res)
        else:
            res = 0
            
    if len(tline) < 37:
        print(tline, len(tline))
    if mx1 > 4:
        print("mx1:", mx1)
    return mx if len(tline) == 37 else -1


def req(n, d, cnt, cnt0 = 0, i = 0):
    if i == len(d):
        return go(d)
    if cnt0 == cnt:
        d[keys[i]][2] = 0
        return req(n, d, cnt, cnt0, i + 1)
    result = -5
    for id in range(min(xddd[keys[i]], n)):
        d[keys[i]][2] = id
        result = max(result, req(n, d, cnt, cnt0 + int(id != 0), i + 1))
        if i == 0:
            print(result)
    return result


d = {0: [{}, 0, 0]}
with open("22.txt") as file:
    for i in file: # или file.readlines()
        x, time, *y = map(int, i.replace(";", " ").split())
        d[x] = [set(y), time, 0]

keys = sorted(d.keys())

ddd = {0: 38, 101: 2, 102: 29, 103: 2, 104: 20, 105: 2, 106: 19, 107: 2, 108: 2, 109: 1, 110: 1, 111: 9, 112: 1, 113: 13}
#print(go(d))
print(req(10, d, 5))

Чтобы оставить комментарий нужна авторизация

Печать