.04 Пары/тройки чисел, выбрать из каждой, кратность

Неэффективный переборный алгоритм для малых N

f = open(’27.txt’)
n = int(f.readline())
a = []
minim = 10000000000000000
for i in range(n):
    a.append([int(x) for x in f.readline().split()])
for i in range(2 ** n):
    num = i
    s = 0
    for j in range(n):
        s += a[j][num % 2]
        num //= 2
    if s < minim and s % 8 == 0:
        minim = s
print(minim)

Эффективный алгоритм

f = open(’27.txt’)  # Открываем нужный файл
n = int(f.readline())

k = 8  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список для хранения минимальных разностей по остаткам
s = 0  # Переменная для минимальной суммы
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    s += min(a, b)  # Прибавляем к сумме минимальное число из пары
    r = abs(a - b)  # Разность между элементами

    mr1 = mr[:]  # Создаём копию списка разностей
    for j in range(k):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % k]:
            mr[(r + mr1[j]) % k] = r + mr1[j]

    # Если текущая разность меньше разности в списке
    if r < mr[r % k]:
        mr[r % k] = r

# Если сумма в итоге не кратна k
if s % k != 0:
    # Прибавляем к мин. сумме разность с недостающим остатком
    s += mr[k - s % k]

print(s)