Я ищу помощь в следующей задаче:
Формулировка задачи: Вам дан массив из N чисел (положительные, отрицательные, целые числа, числа от -100 до 100).
Разбейте массив на k непересекающихся, смежных подмассивов так, чтобы при:
- Вычислить сумму каждого подмассива и затем
- Вычислить дисперсию этих суммы.
, что дисперсия будет минимизирована.
Ограничения: Минимальная длина любого подмассива должна быть больше или равна l_min. Максимальная длина любого подмассива должна быть меньше или равна l_max. Максимальное значение: 10 ^ 9
Входные данные: np.array, k, l_min, l_max, adj_min, adj_max
где:
, если adj_min = 1 и adj_max = 1 вложенные массивы являются дополнительными (индексное расстояние между концом n и началом массива n + 1 равно 1)
, если adj_min = a и adj_max = b индексное расстояние между концом n и началом массива n + 1 должно быть минимумом a и максимумом b.
Выходные данные: последовательность последовательных индексов, описывающих границы подмассивы относительно данного массива 'master'. Примером такой последовательности для массива длиной N = 30, k = 4, l_min = 4, l_max = 10 ^ 9, adj_min = 1, adj_max = 1 будет: массив ([0 10 11 17 18 22 23 29 ]), что переводится в деление (0 10 | 11 17 | 18 22 | 23 29)
Убедитесь, что:
- нет двойных индексов (чтобы избежать дублирования)
- разница в индексе между: i) границей конца предыдущего подмассива и ii) границей начала следующего подмассива, равной или большей 1 (чтобы обеспечить -массивы смежны или разделены допустимыми расстояниями, как указано в adj_min и adj_max. Обратите внимание, что расстояния между различными подмассивами не обязательно должны быть одинаковыми)
Дополнительные комментарии:
- Не используйте библиотеки, предлагающие решатели оптимизации.
- Исключите (сгенерируйте сообщение об ошибке) для недопустимой комбинации входных данных, например: N = 10, k = 5, l_min = 4 (если мы разделив 10 на 5, мы получим «принудительную» минимальную длину подмассива 2, cts l_min = 4)
Мои попытки: На этом этапе моих навыков проблема огромна, и я чувствую, что мне потребуется еще несколько месяцев практики для решения сложных задач динамического программирования c, чтобы подойти к нему сам. Даже практика популярных проблем с разбиением подмассива не помогает мне решить эту проблему, поскольку они намного проще. Однако эта проблема очень интересна, и я хотел бы изучить решение, хотя, возможно, пока не до конца ее понимаю. Если бы кто-то мог предложить помощь в преодолении этой проблемы и / или указать правильное направление с точки зрения соответствующей литературы, было бы здорово. Спасибо!