Недавно я столкнулся со следующей проблемой, и до сих пор не понял, как ее решить.
Пусть S = {v1, v2, v3, ..., vn} — набор из n массивов, определенных на ℝ6. То есть в каждом массиве по 6 записей.
Пусть для заданного набора массивов среднее значение измерения будет средним значением между координатами, соответствующими этому измерению, для всех элементов набора.
Кроме того, давайте определим определенное свойство P набора массивов как наименьшее значение среди всех средних значений набора (всего имеется 6 средних значений, по одному для каждого измерения). Например, если в некотором наборе в качестве среднего значения размеров измерения используется {10, 4, 1, 5, 6, 3}, то P для этого набора равен 1.
Теперь к определению задачи: вернуть максимальное количество элементов среди всех подмножеств S' множества S, таких что P(S') ≥ T, T известное пороговое значение, или 0, если такое подмножество не существует. Кроме того, выведите любое максимальное S' (такое, что P(S') ≥ T).
Резюмируя: Входы: множество S и пороговое значение T. Выход: Некоторое подмножество S' (|S'| очевидно непосредственно).
Сначала я начал пытаться придумать жадное решение, но безуспешно. Затем я перешел к подходу динамического программирования, но не смог установить рекурсию, которая решила проблему. Я мог бы немного расширить свои мысли о решении, но я не думаю, что они будут очень полезны, учитывая, как далеко я продвинулся (или не продвинулся).
Любая помощь будет принята с благодарностью!
