02
Дек
2017

Найти максимальную площадь матрицы с суммой элементов меньше или равной k

Могли бы вы посоветовать алгоритм, решающий следующую задачу?

Задана прямоугольная матрица размером nxm и число k. Нужно найти подматрицу (исходная матрица также считается подматрицей) наибольшей площади (число столбцов умноженное на число строк), у которой сумма элементов меньше или равна k. Вернуть площадь этой матрицы. Все элементы матрицы и число k - положительные целые числа. Алгоритм должен иметь сложность ниже О(n^6). Можно использовать дополнительные структуры на основе матрицы.

На данный момент понял, что могут помочь матрицы сумм столбцов и строк: матрица сумм столцов для матрицы с элементами вида

equation

матрица сумм строк:

equation

матрица сумм столбцов:

equation

То есть для матрицы вида

equation

матрица сумм строк:

equation

матрица сумм столбцов:

equation

eще прочитал, что можно использовать матрицу сумм подматриц вида

equation

которая для приведенной матрицы выглядит так

equation

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

equation

матрицы

equation

как equation

Источник: https://ru.stackoverflow.com/questions/752807/%D0%9D%D0%B0%D0%B9%D1%82%D0%B8-%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%83%D1%8E-%D0%BF%D0%BB%D0%BE%D1%89%D0%B0%D0%B4%D1%8C-%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8B-%D1%81-%D1%81%D1%83%D0%BC%D0%BC%D0%BE%D0%B9-%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%D0%BE%D0%B2-%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B5-%D0%B8%D0%BB%D0%B8-%D1%80%D0%B0%D0%B2%D0%BD%D0%BE%D0%B9-k

Тебе может это понравится...

Добавить комментарий