Оптимальное распределение задач

Question

Задача звучит так: У вас есть 2-ядерный процессор и программа, состоящая из n независимых задач, которую нужно максимально быстро выполнить на этом процессоре, распределив задачи между 2 ядрами. Время выполнения задачи j это p_j. Задачи нельзя прерывать во время выполнения. Напишите псевдокод алгоритма, который распределяет задачи по 2 ядрам так, чтобы время завершения всей программы (то есть время завершения последней задачи) было минимально. Покажите, какую вычислительную сложность имеет ваш алгоритм и почему. Считайте, что размер массива p_j, не более 10^3, а его элементы - целые числа от 1 до 10^4

Я пробовал делать так, сортировать все числа за O(nlog n) и жадным алгоритмом распределять время выполнения этих задач за O(n). Например есть массив из 20 элементов:

[13, 64, 61, 88, 1, 58, 47, 31, 97, 42, 92, 87, 99, 72, 26, 29, 73, 64, 57, 100]

Отсортировав, получаем

[1, 13, 26, 29, 31, 42, 47, 57, 58, 61, 64, 64, 72, 73, 87, 88, 92, 97, 99, 100]

И теперь на каждое ядро поочередно берем максимальное время, то есть
на 1 ядро: [100, 97, 88, 73, 64, 61, 57, 42, 29, 13] - общая сумма времени = 624
на 2 ядро: [99, 92, 87, 72, 64, 58, 47, 31, 26, 1] - общая сумма времени = 577
И теперь попытаться прировнять эти суммы. Будем брать последовательно минимальное число из ядра, у которого сумма времени больше. Проверяем
624 - 13 = 611 и 577 + 13 = 590 разница 21.
624 - 29 = 595 и 577 + 29 = 606 разница 11.
624 - 42 = 582 и 577 + 42 = 619 разница 37.
И в конце смотрим, что можно переложить из второго ядра в первое (с учетом того, что мы закинули 11 в 2 ядро)
606 - 1 = 605 и 595 + 1 = 596 разница 9.
Время выполнения O(n log n + n + n) = O(n log n). Скорее всего это решение неправильно, подскажите как можно решить такую задачу, какие алгоритмы использовать?

Answer 1

По сути, вам нужно разбить набор чисел на две части так, чтобы разница между ними была минимальной. Этого можно добиться с использованием динамического программирования, реализуя алгоритм из когорты "subset sum" - набрать такое подмножество, чтобы его сумма была как можно ближе к половине суммы всего набора.

Величина чисел ограничена, сложность получается O(N*общаясумма)

Вот пример реализации на Python ( a = [0] * best создаёт список длины best, заполненный нулями) c восстановлением нужного подмножества (второе - оставшиеся элементы). Объяснение здесь уже приводил

def halfsum(lst):
    halfs = sum(lst) // 2
    best = halfs + 1
    a = [0] * best
    a[0] = -1
    for l in lst:
        for i in range(halfs, l-1, -1):
            if (a[i - l] !=0) and a[i] == 0:
                a[i] = l
                best = min(halfs - i, best)
    id = halfs - best
    b = []
    while (id > 0):
        b.append(a[id])
        id = id - a[id]
    return b

print(halfsum([3,11,29,53,13,7]))

БЛОГ НА HUSL

Оптимальное распределение задач

Ответы (1 шт):