Как решить данную задачу на python?

Question

[ZykaMyzyka]

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел делилась на 4 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Пример входного файла:
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12
Для указанных входных данных значением искомой суммы должно быть число 88.
Нужно универсальное решение, которое всегда найдёт решение, а не половинное (нашло максимальную сумму, а дальше как повезет)

Answer 1

[Wataru]

Динамическое программирование.

F(i,k) - максимальная сумма, которую можно получить из первых i троек, такая что ее остаток от деления на 4 равен k.

База: F(0,0) = 0, F(0,k) = -infinity.
Ответ: F(n, 0).

Пересчет

F(i,k) = max(F(i-1, ((k-a[i][0]-a[i][1])%4+4)%4)+a[i][0]+a[i][1], 
             F(i-1, ((k-a[i][1]-a[i][2])%4+4)%4)+a[i][1]+a[i][2], 
             F(i-1, ((k-a[i][0]-a[i][2])%4+4)%4)+a[i][0]+a[i][2])

Только лучше вместо -infinity как-то отмечать, что позиция (i,k) недопустима (нельзя первыми i тройками набрать сумму с остатком k. И недопустимые варианты при выборе максимума выбирать ненадо.

Еще, вместо перебора всех пар из трех элементов лучше брать сумму трех и вычитать один, который перебирается циклом.

Comments

[ZykaMyzyka]

Завтра запущу на файл из 6000 строк посмотрим, как работает. Я сделал решение данной задачи, но не до конца. Код также завтра скину. Спасибо за помощь!