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