Постановка задачи: у меня N списков номеров. Я должен взять один элемент из каждого списка и не могу взять более одного числа из любого списка. Рассчитайте максимальную сумму. Я думаю, что это проблема NP-Hard. Если это действительно проблема NP-Hard, какое предположение может сделать ее проблемой полиномиальной сложности? Это настоящая отраслевая проблема.
Возьмите максимум каждого списка и суммируйте его.
в питоне:
data = [[1, 2, 1], [3, 2, 1], [0, -1, 2]] result = sum(max(sub) for sub in data) # -> 7
сложность = O(n), где n - общее количество элементов в подсписках
O(n)
n