Выбор записи из каждого столбца матрицы и взятие их суммы
У меня есть матрица MXN действительных чисел. Как я могу найти все способы выбора одной записи из каждого столбца так, чтобы их сумма была больше некоторого порогового значения? Наивным способом было бы проверить все способы, но есть ли какие-нибудь умные способы сделать это, которые немного уменьшают сложность? Я предполагаю, что вы не можете разорвать границу O(m^n), но, возможно, другой алгоритм может немного уменьшить константу впереди?
Кроме того, если эта проблема, по сути, является известной (или похожей), пожалуйста, дайте мне знать. Заранее спасибо.
Некоторые небольшие улучшения:
Если порог достаточно высок, есть некоторые элементы матрицы, которые вы никогда не выберете, просто потому, что независимо от того, какие другие записи вы выбираете из других столбцов, сумма не может быть достаточно высокой. Мы можем устранить их при предварительной обработке.
Поскольку вы выбираете записи слева направо и обнаруживаете, что независимо от того, как вы выбираете записи из оставшихся столбцов, просто выходите.
Изменить: Я хотел бы получить позиции выбранных значений!
2 ответа
Вот алгоритм, основанный на ваших улучшениях, который работает только на постоянный коэффициент дольше, чем это необходимо для записи всех выходных данных.
Перед началом сортируйте в каждом столбце от наибольшего к наименьшему и вычисляйте суммы суффиксов первой строки (т. Е. Сканируйте справа налево, чтобы определить для каждого j максимальный вклад столбцов j..n).
Теперь выполните рекурсивный поиск по правилу сокращения: для текущего столбца попробуйте значения от наибольшего к наименьшему и выполните рекурсивный анализ, вырвавшись из цикла строк, если максимальный вклад оставшихся столбцов плюс сумма на данный момент меньше порогового значения.
Для анализа посмотрите на дерево рекурсии. Каждый лист - решение, которое, имея размер n, платит за каждого предка. Постоянные накладные расходы на каждом узле.
Если каким-то образом вы можете использовать каждое решение в сублинейное время, возможно, путем взаимосвязи производителя и потребителя, есть другая оптимизация, которая понижает вычисление до O(1) вместо O(n), определяя, когда необходимо взять все оставшиеся максимумы. Это достигается путем сортировки столбцов по разрыву между самым большим и вторым по величине элементом; затем, как только есть один выбор для столбца, идущего слева направо, другие тоже вынуждены.
Является ли положение значений, выбранных в матрице, проблемой, или вы просто хотите узнать значения, выбранные в каждом столбце для каждого пути?
Если это второй вариант, то упорядочение значений в каждом столбце позволит вам обрезать поиск, как только значение в столбце перестанет его удовлетворять. например:
8 7 4 9 2
5 6 4 8 2
3 3 2 3 1
2 2 2 1 1
предположим, что ваш порог равен 25, а затем, выбрав 8, 7, 4, 3, 2, вы можете остановить поиск в 4-м и 5-м столбцах для значений 8,7,4 в столбцах 1, 2 и 3. И так далее.,