У меня есть M = 20 массивов P_i длиной N = 2000 каждый. Каждый массив представляет собой дискретное распределение вероятностей.
Пусть r - массив из 20 индексов. Let P[r] = P_1[r_1] * P_2[r_2] * ... * P_20[r_20].
Также let L = sum(r)
Я хотел бы вычислить
S = sum(P[r] for all r s.t. L(r) > L0), где L0 - некоторое известное натуральное число
Точный ответ: не требуется - двух di git точности должно быть достаточно.
Наивный алгоритм грубой силы для вычисления S требует O (N ^ M), что невозможно. Есть что-нибудь лучше?